C/C++ | 并查集：用于检查一个图上有没有环 - C++

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

没有环的过程分析：

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#define VERTICES 6
#define LINE 5
using namespace std;/*
parent:数组解决并查集合并问题
VERTICES:设定的顶点数
LINE:设定的边数
*/
void initialise(int *parent)
{
//用于parent数组的初始化
int i;
for(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;}
int union_vertices(int x,int y,int parent[])
{
//用于合并两个集合。返回0：合并成功，返回1：合并失败
int x_root=find_root(x,parent);
int y_root=find_root(y,parent);
printf("x:当前数是%d,他的parent是：%d\n",x,x_root);
printf("y:当前数是%d,他的parent是：%d\n",y,y_root);if(x_root==y_root)
{
return 0;
}
else
{
parent[x_root]=y_root;//将x连到y上
return 1;
}}
int main()
{
int parent[VERTICES]={0};
initialise(parent);
int edges[LINE][2] = {
{0,1},{1,2},{1,3},
{2,4},{2,5}
};
for(int i=0;i<LINE;++i)
{
int x=edges[i][0];
int y=edges[i][1];
if(union_vertices(x,y,parent)==0)
{
printf("存在环");
exit(0);
}
}
printf("没有环");
return 0;
}

最后一次执行了“parent[x_root]=y_root;”,所以4的parent变成了5

存在环的过程分析：

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#define VERTICES 6
#define LINE 6
using namespace std;/*
parent:数组解决并查集合并问题
VERTICES:设定的顶点数
LINE:设定的边数
*/
void initialise(int *parent)
{
//用于parent数组的初始化
int i;
for(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;}
int union_vertices(int x,int y,int parent[])
{
//用于合并两个集合。返回0：合并成功，返回1：合并失败
int x_root=find_root(x,parent);
int y_root=find_root(y,parent);
printf("x:当前数是%d,他的parent是：%d\n",x,x_root);
printf("y:当前数是%d,他的parent是：%d\n",y,y_root);if(x_root==y_root)
{
return 0;
}
else
{
parent[x_root]=y_root;//将x连到y上
return 1;
}}
int main()
{
int parent[VERTICES]={0};
initialise(parent);
int edges[LINE][2] = {
{0,1},{1,2},{1,3},
{2,4},{2,5},{3,4}
};
for(int i=0;i<LINE;++i)
{
int x=edges[i][0];
int y=edges[i][1];
if(union_vertices(x,y,parent)==0)
{
printf("存在环");
exit(0);
}
}
printf("没有环");
return 0;
}

最后一次没有执行“parent[x_root]=y_root;”

路径压缩：

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#define VERTICES 6
#define LINE 6
using namespace std;void initialise(int *parent,int rank[])
{int i;
for(i=0;i<VERTICES;i++)
{
parent[i]=-1;
rank[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;}
int union_vertices(int x,int y,int parent[],int rank[])
{int x_root=find_root(x,parent);
int y_root=find_root(y,parent);
printf("x:当前数是%d,他的parent是：%d,他的rank是：%d\n",x,x_root,rank[x]);
printf("y:当前数是%d,他的parent是：%d,他的rank是：%d\n",y,y_root,rank[y]);if(x_root==y_root)
{
return 0;
}
else
{
if(rank[x_root] > rank[y_root])
{
parent[y_root]=x_root;
}
else if(rank[y_root]>rank[x_root])
{
parent[x_root]=y_root;
}
else
{
parent[x_root]=y_root;
rank[y_root]++;
}
return 1;
}}
int main()
{
int parent[VERTICES]={0};
int rank[VERTICES]={0};
initialise(parent,rank);
int edges[LINE][2] = {
{0,1},{1,2},{1,3},
{2,4},{2,5},{3,4}
};
for(int i=0;i<LINE;++i)
{
int x=edges[i][0];
int y=edges[i][1];
if(union_vertices(x,y,parent,rank)==0)
{
printf("存在环");
exit(0);
}
}
printf("没有环");
return 0;
}