首页 > 代码库 > 并查集(1)-判断无向图是否存在环

并查集(1)-判断无向图是否存在环

并查集是一种树型的数据结构,用于处理一些不相交集合(Disjoint Sets)的合并及查询问题。常常在使用中以森林来表示。集就是让每个元素构成一个单元素的集合,也就是按一定顺序将属于同一组的元素所在的集合合并。

  • Find:确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集合。
  • Union:将两个子集合并成同一个集合。

其实判断一个图是否存在环已经有相应的算法,此文用并查集来判断一个图是否有环。

我们可以用一个一维数组parent[] 来记录子集合。

看下面这个图:

0|  |    1-----2

对每一条边的两个顶点加入集合,发现两个相同的顶点在一个子集合中,就说明存在环。

初始化:parent[n] 的每个元素都为-1,共有n个子集合,表示集合只有当前顶点一个元素。

0 1 2-1 -1 -1

然后逐个处理每条边。

边0-1:我们找到两个子集合 0 和1,因为他们在不同的子集合,现在需要合并他们(Union). 把其中一个子集合作为对方的父集合.

0   1   2    <----- 1 成为 0 的 父集合 (1 现在代表集合 {0, 1})1  -1  -1

边0-2:1属于属于子集合1,2属于子集合2,因此合并他们。

0   1   2    <----- 2 作为 1的父集合 (2 现在代表集合 {0, 1, 2})1   2  -1

 边0-2: 0是在子集和2和2也是在子集合2, 因为 0->1->2 // 1 是0 父集合 并且  2 是1的父集合 。因此,找到了环。

代码:

// 用并查集判断是否存在环#include <stdio.h>#include <stdlib.h>#include <string.h>// 图中的边struct Edge{    int src, dest;};// 图结构体struct Graph{    // V-> 顶点个数, E-> 边的个数    int V, E;    // 每个图就是 边的集合    struct Edge* edge;};// 创建一个图struct Graph* createGraph(int V, int E){    struct Graph* graph = (struct Graph*) malloc( sizeof(struct Graph) );    graph->V = V;    graph->E = E;    graph->edge = (struct Edge*) malloc( graph->E * sizeof( struct Edge ) );    return graph;}// 查找元素i 所在的集合( 根 )int find(int parent[], int i){    if (parent[i] == -1)        return i;    return find(parent, parent[i]);}// 合并两个集合void Union(int parent[], int x, int y){    int xset = find(parent, x);    int yset = find(parent, y);    parent[xset] = yset;}// 检测环int isCycle( struct Graph* graph ){    int *parent = (int*) malloc( graph->V * sizeof(int) );    // 初始化所有集合    memset(parent, -1, sizeof(int) * graph->V);    // 遍历所有边    for(int i = 0; i < graph->E; ++i)    {        int x = find(parent, graph->edge[i].src);        int y = find(parent, graph->edge[i].dest);        if (x == y) //如果在一个集合,就找到了环            return 1;        Union(parent, x, y);    }    return 0;}// 测试int main(){    /* 创建一些的图         0        |          |            1-----2 */    struct Graph* graph = createGraph(3, 3);    // 添加边 0-1    graph->edge[0].src = http://www.mamicode.com/0;    graph->edge[0].dest = 1;    // 添加边 1-2    graph->edge[1].src = http://www.mamicode.com/1;    graph->edge[1].dest = 2;    // 添加边 0-2    graph->edge[2].src = http://www.mamicode.com/0;    graph->edge[2].dest = 2;    if (isCycle(graph))        printf( "Graph contains cycle" );    else        printf( "Graph doesn‘t contain cycle" );    return 0;}