并查集（Disjoint Set）_并查集求奇环

七、并查集（Disjoint Set）

1、引入

并查集是用于检查图中是否存在环状结构的。

列：

 

通过并查集检测上诉图中是否有环

（1）、先将六个顶点平铺开来

（2）、 将两边相连的顶点放入一个结合中

此时的集合将有两个性质： ​

①集合中的每一个顶点都可以通向另一个顶点

②如果从此集合中任选两个顶点就会构成一个环

（3）、用一维数组构成树

①0的父节点是1：parent[0]=1;

②2的父节点是1：parent[2]=1;

得到：

 

 

③3的父节点是4：parent[3]=4;

得到：

（4）、合并父节点

（5）、寻找其中两个顶点的根

如果两个顶点的根相同，则可得到一个环。

2、实现

#define Vertices 6
 
//初始化数组
void initialise(int parent[])
{
    int i;
    for(i=0;i<Vertices;i++)
    {
        parent[i]=-1; 
    }
}
 
//寻找根节点
int find_root(int x,int parent[])
{
    //先假设一个根结点x_root
    int x_root=x;	
    //如果parent[x_root]为-1代表找到根结点
    while(parent[x_root]!=-1)
    {
        //不然就找向上一个顶点
        x_root=parent[x_root];
    }
    return x_root;
}
 
//合并两个树
//如果return 1则合并成功，如果return 0则合并失败
int union_vertices(int x,int y,int parent[])
{
    //寻找x和y两棵树的根结点
    int x_root=find_root(x,parent);
    int y_root=find_root(x,parent);
    //如果两棵树的根结点相同则合并失败
    if(x_root==y_root)
    {
        return 0;
    }
    else
    {
        //把x的根结点连接向y的根节点
     	parent[x_root]=y_root;
        return 1;
    }
}
 
int mian()
{
    int parent[Vertices]={0};
    initialise(parent);
    int edges[6][2]={
        {0,1},{1,2},{1,3},
        {2,4},{3,4},{2,5}
    }
    int i=0;
    for(i=0;i<6;i++)
    {
        int x=edges[i][0];
        int y=edges[i][1];
        if(union_vertices(x,y,parent)==0)
        {
            printf("图中有环\n");
            exit(0);
        }
    }
    printf("图中没有环!\n");
    return 0;
}

方便大家对照的： 

 压缩路径

//未压缩
int find(int x)
{
	if (x==parent[x])return x;
	return find(parent[x]);
}
//压缩后
int find(int x)
{
    if(x==parent[x]) return x;
    //每次都将对应的根存储在对应的叶上
    else parent[x]=find(parent[x]);
    return parent[x];
}

秩序合并

void union(int lx,int ly)//传入x、y
{
    x_root=find(x);						//寻找 x的代表元
    y_root=find(y);						//寻找 y的代表元
    if(x_root==y_root) return ;			//如果 x和 y的代表元一致，说明他们共属同一集合，则不需要合并，直接返回；否则，执行下面的逻辑
    if(rank[x]>rank[y]) pre[y]=x;		//如果 x的高度大于 y，则令 y的上级为 x
    else								//否则
    {
        if(rank[x]==rank[y]) rank[y]++;	//如果 x的高度和 y的高度相同，则令 y的高度加1
        pre[x]=y;						//让 x的上级为 y
    }
}

 时间匆匆，唯有记录才可留下。欢迎斧正、交流。