算法设计------利用并查集检测无向图的环

发表于 | 分类于 ，

并查集

定义：并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。常常在使用中以森林来表示。

核心思想

  • 以一颗有根树代表每个集合。
  • 每个节点维护一个指向其父节点的链接。
  • 对于每个集合根节点为该集合的代表。
  • 例如： 集合{x,y,z}和{a,b,c,d}。

主要操作

  • Find(X):查找元素X所在集合，可用于确定两个元素是否在相同的子集中。
  • Union(x,y):将元素x，y所在的两个集合中合并为一个集合。

并查集实现

简单实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// Naive implementation of find
int find(int parent[], int i)
{
    if (parent[i] == i)
        return i;
    return find(parent, parent[i]);
}
  
// Naive implementation of union()
void Union(int parent[], int x, int y)
{
    int xset = find(parent, x);
    int yset = find(parent, y);
    parent[xset] = yset;
}

上面的Union()和Find()实现,最坏的情况下,会产生一个很深的树，成一个链表，find()的时间复杂度是线性的O(n)。以下是一个最坏情况的示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
假设有四个元素0，1，2，3

最初每个元素为一个单元素子集
0 1 2 3 

执行 Union(0, 1)
   1   2   3  
  /
 0

执行 Union(1, 2)
     2   3   
    /
   1
 /
0

执行 Union(2, 3) 
         3    
        /
      2
     /
   1
 /
0

Union()优化：按秩合并

按秩合并，即合并时总是在更深的树根下附加更小深度的树。此时，最坏情况下，find()的时间复杂度为O(Logn)。以下为按秩合并示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
最初每个元素为一个单元素子集
0 1 2 3

执行 Union(0, 1)
   1   2   3  
  /
 0

执行 Union(1, 2)
   1    3
 /  \
0    2

执行 Union(2, 3)
    1    
 /  |  \
0   2   3

find()优化：路径压缩

路径压缩，即在执行find(x)时，“顺便”将x的父节点改为查找到的根节点，以后再调用find(x)就只需O(1)的时间且如果x是子树的根，那么子树的所有节点到根节点的路径都会被压缩。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
假设在如下子集调用find(3)
              9
         /    |    \  
        4     5      6
     /     \        /  \
    0        3     7    8
            /  \
           1    2  

在执行find(3)时，我们“顺便”将3的父节点指向9，当下一次调用find()参数为1，2，3时，其到根节点的路径都会被压缩。

               9
         /    /  \    \
        4    5    6     3 
     /           /  \   /  \
    0           7    8  1   2

按秩合并和路径压缩两种优化下的并查集，find()的时间复杂度小于O(Logn)。

并查集应用——检测无向图中的环

原理：对于图的每个边，找到每个边的两个顶点集，如果两个顶点集相同，则找到一个环。

C语言实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <stdio.h>
#include <stdlib.h>
 
// 边结构
struct Edge
{
    int src, dest;
};
 
// 图结构
struct Graph
{
    // V-> 顶点的数量, E-> 边的数量
    int V, E;
 
    // 图是一个边的集合
    struct Edge* edge;
};

struct subset
{
    int parent;
    int rank;
};
 
// 创建图
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;
}
 
// 以路径压缩方式实现find()
int find(struct subset subsets[], int i)
{
    // find root and make root as parent of i (path compression)
    if (subsets[i].parent != i)
        subsets[i].parent = find(subsets, subsets[i].parent);
 
    return subsets[i].parent;
}
 
// 以按秩合并实现Union()
void Union(struct subset subsets[], int x, int y)
{
    int xroot = find(subsets, x);
    int yroot = find(subsets, y);
 
    // 在更深的树的根下附加更浅的树
    if (subsets[xroot].rank < subsets[yroot].rank)
        subsets[xroot].parent = yroot;
    else if (subsets[xroot].rank > subsets[yroot].rank)
        subsets[yroot].parent = xroot;
 
    // 两个树的深度相同，rank++
    else
    {
        subsets[yroot].parent = xroot;
        subsets[xroot].rank++;
    }
}
 
//检测给定图中是否有环
int isCycle( struct Graph* graph )
{
    int V = graph->V;
    int E = graph->E;
 
    // 每个顶点初始化为一个集合
    struct subset *subsets =
        (struct subset*) malloc( V * sizeof(struct subset) );
 
    for (int v = 0; v < V; ++v)
    {
        subsets[v].parent = v;
        subsets[v].rank = 0;
    }
 
  
    // 遍历图的所有边，找到每个边的两个顶点集，如果集相同，则在图中有循环。
    for(int e = 0; e < E; ++e)
    {
        int x = find(subsets, graph->edge[e].src);
        int y = find(subsets, graph->edge[e].dest);
 
        if (x == y)
            return 1;
 
        Union(subsets, x, y);
    }
    return 0;
}
 
//测试代码
int main()
{
    /* 创建如下图
         0
        |  \
        |    \
        1-----2 */
 
    int V = 3, E = 3;
    struct Graph* graph = createGraph(V, E);
 
    // 边 0-1
    graph->edge[0].src = 0;
    graph->edge[0].dest = 1;
 
    // 边 1-2
    graph->edge[1].src = 1;
    graph->edge[1].dest = 2;
 
    // 边 0-2
    graph->edge[2].src = 0;
    graph->edge[2].dest = 2;
 
    if (isCycle(graph))
        printf( "Graph contains cycle" );
    else
        printf( "Graph doesn't contain cycle" );
 
    return 0;
}

如果对你有帮助的话，Star✨下一吧！