并查集（Disjoint Set）用来判断已有的数据是否构成环。

在构造图的最小生成树（Minimum Spanning Tree）时，如果采用 Kruskal 算法，每次添加最短路径前，需要先用并查集来判断一下这个路径是否会构成环。

思路

遍历图的每一条边，按照下面的原则将对应的两个顶点添加到集合中：

如果两个顶点都不属于任一集合，则创建新的集合，并将这两个顶点放入如果两个顶点都已经属于某个集合，则已经构成环，退出如果有一个顶点已经属于某个集合，则将另一个顶点也加入这个集合

为了代码上的统一性，可以在开始前，把所有顶点都看成只有一个元素的集合，然后就是不停的合并集合。

集合可以用树的双亲表示法来表示，只需要额外创建一个数组即可。为了简化合并操作，可以每次都只操作两颗树的根结点。

int parent[n]; // 查找树的根结点 int findRoot(int parent[], int key) { int root = key; while (parent[root] != -1) { root = parent[root]; } return root; } // 合并树 int unionVertex(int parent[], int x, int y) { int lRoot = findRoot(parent, x); int rRoot = findRoot(parent, y); // 两个结点的根结点为同一个，则这两个结点属于同一棵树 if (lRoot == rRoot) { return 0; } // 否则，合并树，这里直接把左树作为右树的子树，可能会导致不平衡 parent[lRoot] = rRoot; }

代码

为了在每次合并时，尽可能保证树的平衡，再创建一个数组保存树的高度，合并时将高度低的树作为子树即可。

#include <stdio.h> void init(int parent[], int height[], int count) { int i; for (i = 0; i < count; i++) { parent[i] = -1; height[i] = 0; } } int findRoot(int parent[], int key) { int root = key; while (parent[root] != -1) { root = parent[root]; } return root; } int unionVertex(int parent[], int height[], int x, int y) { int lRoot = findRoot(parent, x); int rRoot = findRoot(parent, y); if (lRoot == rRoot) { return 0; } // parent[lRoot] = rRoot; if (height[lRoot] < height[rRoot]) { parent[lRoot] = rRoot; } else if (height[rRoot] < height[lRoot]) { parent[rRoot] = lRoot; } else { parent[lRoot] = rRoot; height[rRoot]++; } return 1; } int main(void) { int edgeCount = 6, vertexCount = 5; int i; // 图中的边 int graph[5][2] = { {0, 1}, {2, 4}, {1, 2}, {1, 3}, {2, 5} }; int parent[edgeCount]; int height[edgeCount]; init(parent, height, edgeCount); for (i = 0; i < vertexCount; i++) { int ret = unionVertex(parent, height, graph[i][0], graph[i][1]); if (ret == 0) { printf("%d, %d\n", graph[i][0], graph[i][1]); printf("find cycle!\n"); return 0; } } printf("no find cycle!\n"); for (i = 0; i < vertexCount; i++) { printf("%d's parent is: %d\n", i, parent[i]); } for (i = 0; i < vertexCount; i++) { printf("%d's height is: %d\n", i, height[i]); } return 0; }

执行结果：

no find cycle! 0's parent is: 1 1's parent is: 4 2's parent is: 4 3's parent is: 4 4's parent is: -1 0's height is: 0 1's height is: 1 2's height is: 0 3's height is: 0 4's height is: 2

转载于:https://www.cnblogs.com/kika/p/10851497.html