判断一个图里是否有环

电玩女神 2021-12-12 22:31 247阅读 0赞

题目：利用并差集（disjoint\_set)判断一个图里是否有环

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdqaWFuNTMw_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdqaWFuNTMw_size_16_color_FFFFFF_t_70 1][]

一般代码：

/*利用并差集（disjoint_set)判断一个图里是否有环 */
    #include <iostream>
    # define VERTICES 6 //设置图的定点为6个 
    using namespace std;
    
    //初始化根结点数组,此时每个结点都是一个独立的结点 
    void initalise(int parent[]) { 
    	for(int i=0; i<VERTICES; i++) {
    		parent[i] = -1;
    	} 
    } 
    
    //查找根结点 
    int find_root(int x, int parent[]) {
    	int x_root = x; //假设要找的结点就是根结点
    	while(parent[x_root] != -1) { //从当前结点一直往上寻找根结点
    		x_root = parent[x_root]; 	 
    	} 
    	return x_root;
    }
    
    //合并结点x,y，合并成功返回1，失败返回0 
    int union_vertices(int x, int y, int parent[]) {
    	int x_root = find_root(x, parent); //合并两个结点之前得先找到他们的根结点，然后然其中一个指向一方即可 
    	int y_root = find_root(y, parent);
    	if(x_root == y_root) { //如果x和y同属于一个根结点下，则不用合并 
    		return 0;
    	} 
    	else {
    		parent[x_root] = y_root; //x的根结点指向y的根结点
    		return 1; 
    	} 
    } 
    int main(){
    	int parent[VERTICES] = {0};//parent数组用来表示当前结点的根结点 
    	int edges[6][2] = { //导入图的边 
    	{0, 1}, {1, 2}, {1, 3}, 
    	{2, 4}, {3, 4}, {2, 5}
    	};
    	initalise(parent);
    	for(int i=0; i<6; i++) {
    		int x = edges[i][0]; //第i条边的第一个数字 
    		int y = edges[i][1]; //第i条边的第二个数字 
    		if(union_vertices(x ,y , parent) == 0) {
    			cout << "Cycle detected!" << endl ; //图里有环
    			exit(0); //直接退出结束 
    		} 
    	} 
    	cout << "No Cycle found." << endl; //图里无环 
    	return 0;
    }

优化后的代码：

当图是类似于只有右子树或者只有左子树的时候，我们每次从下面开始查找都要查找n次，为了降低时间复杂度,我们得在查找根结点的过程中压缩路径

/*利用并差集（disjoint_set)判断一个图里是否有环 */
    #include <iostream>
    # define VERTICES 6 //设置图的定点为6个 
    using namespace std;
    
    //初始化根结点数组,此时每个结点都是一个独立的结点 
    void initalise(int parent[], int height[]) { //height用来表示当前结点的高度 
    	for(int i=0; i<VERTICES; i++) {
    		parent[i] = -1;
    		height[i] = 0;
    	} 
    } 
    
    //查找根结点 
    int find_root(int x, int parent[]) {
    	int x_root = x; //假设要找的结点就是根结点
    	while(parent[x_root] != -1) { //从当前结点一直往上寻找根结点
    		x_root = parent[x_root]; 	 
    	} 
    	return x_root;
    }
    
    //合并结点x,y，合并成功返回1，失败返回0 
    int union_vertices(int x, int y, int parent[], int height[]) {
    	int x_root = find_root(x, parent); //合并两个结点之前得先找到他们的根结点，然后然其中一个指向一方即可 
    	int y_root = find_root(y, parent);
    	if(x_root == y_root) { //如果x的根结点和y的根结点同属于一个根结点下，则不用合并 
    		return 0;
    	} 
    	else {
    		if(height[x_root] > height[y_root]) {
    			parent[y_root] = x_root; //每次将根结点结点矮的并入根结点高的 
    		} else if(height[y_root] > height[x_root] ){
    			parent[x_root] = y_root; //x的根结点指向y的根结点
    		} else {
    			parent[y_root] = x_root; //x和y的根结点高度相同, 直接并过来 
    			height[y_root]++; 
    		}
    		
    		return 1; 
    	} 
    } 
    int main(){
    	int parent[VERTICES] = {0};//parent数组用来表示当前结点的根结点 
    	int height[VERTICES] = {0};
    	int edges[6][2] = { //导入图的边 
    	{0, 1}, {1, 2}, {1, 3}, 
    	{2, 4}, {3, 4}, {2, 5}
    	};
    	
    	initalise(parent, height);
    	for(int i=0; i<6; i++) {
    		int x = edges[i][0]; //第i条边的第一个数字 
    		int y = edges[i][1]; //第i条边的第二个数字 
    		if(union_vertices(x ,y , parent, height) == 0) {
    			cout << "Cycle detected!" << endl ; //图里有环
    			exit(0); //直接退出结束 
    		} 
    	} 
    	cout << "No Cycle found." << endl; //图里无环 
    	return 0;
    }

运行结果：

![20190712213652982.png][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdqaWFuNTMw_size_16_color_FFFFFF_t_70]: /images/20211210/019f3abd522b4e1a83299d8fe33fbc51.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdqaWFuNTMw_size_16_color_FFFFFF_t_70 1]: /images/20211210/9bf02dec79024223b9c0ebc4fdddef72.png
[20190712213652982.png]: /images/20211210/3c15f2ba519949bc957af78928e1c9af.png