Disjoint 集合数据结构或 Union-Find 算法简介
联合查找算法是一种对此类数据结构执行两个有用操作的算法：
- 查找：确定特定元素在哪个子集中。这可用于确定两个元素是否在同一子集中。
- 联合：将两个子集连接成一个子集。这里首先我们必须检查这两个子集是否属于同一个集合。如果否，则我们无法执行联合。
不相交集的 UNION 和 FIND 操作
一组元素 a1、a2、…an 上的关系可以分为等价类。元素 a 的等价类是 S 的子集，它包含 S 中与 a 相关的所有元素。
通过这两个操作将一组元素划分为等价的类
1.联合
2. 寻找
一个集合被分成子集。每个子集都包含相关元素。如果我们知道 ai 和 aj 这两个元素是相关的，那么我们可以执行以下操作：
1.找到子集：包含ai的Si
2.找到子集：包含aj的Sj
3.如果S,和Si是两个独立的子集
然后我们通过合并 Si 和 Sj 创建一个新的子集
新子集 = Si C ∪ PS j 。
该算法是动态的，因为在算法过程中，集合可以通过并集操作改变。
例子：
让我们检查一个例子来理解数据结构是如何应用的。为此，请考虑以下问题陈述
问题：给定一个无向图，任务是检查图中是否包含循环。
例子：
输入：下图
输出：是
解释：存在顶点 {0, 1, 2} 的循环。
我们已经讨论了一种在有向图中检测循环的算法。这里可以使用 Union-Find 算法来检查无向图是否包含循环。这个想法是，
最初创建仅包含一个节点的子集，该节点是其自身的父节点。现在在遍历边时，如果边的两个端节点属于同一个集合，则它们形成一个循环。否则，执行 union 将子集合并在一起。
注意：此方法假定图形不包含任何自环。
插图：
请按照下图更好地理解
让我们考虑下图：
使用数组来跟踪子集以及哪些节点属于该子集。让数组成为parent[]。
最初，父数组的所有槽都被初始化为保存与节点相同的值。
父母 [] = {0, 1, 2}。同样，当节点的值与其父节点的值相同时，即为该节点子集的根。
现在一条一条地处理所有的边。
Edge 0-1:
=> 找到顶点0和1所在的子集。
=> 0 和 1 属于子集 0 和 1。
=> 因为它们在不同的子集中，所以取它们的并集。
=> 要合并，请将节点 0 作为节点 1 的父节点，反之亦然。
=> 1 成为 0 的父级（1 现在代表子集 {0, 1}）
=> parent[] = {1, 1, 2}边 1-2：
=> 1 在子集 1 中，2 在子集 2 中。
=> 因为它们在不同的子集中，所以取并集。
=> 将 2 作为 1 的父级。（2 现在代表子集 {0, 1, 2}）
=> parent[] = {1, 2, 2}边 0-2：
=> 0 在子集 2 中，2 也在子集 2 中。
=> 因为 1 是 0 的父级，而 2 是 1 的父级。所以 0 也属于子集 2
=> 因此，包括这条边形成一个循环。因此，上图包含一个循环。
按照以下步骤来实现这个想法：
- 最初创建一个parent[]数组来跟踪子集。
- 遍历所有边：
- 通过查找 parent[] 数组检查每个节点属于哪个子集，直到节点和父节点相同。
- 如果两个节点属于同一个子集，则它们属于一个循环。
- 否则，对这两个子集执行联合操作。
- 如果没有找到循环，则返回 false。
下面是上述方法的实现。
// A union-find algorithm to detect cycle in a graph
#include <bits/stdc++.h>
using namespace std;
// a structure to represent an edge in graph
class Edge {
public:
int src, dest;
};
// a structure to represent a graph
class Graph {
public:
// V-> Number of vertices, E-> Number of edges
int V, E;
// graph is represented as an array of edges
Edge* edge;
};
// Creates a graph with V vertices and E edges
Graph* createGraph(int V, int E)
{
Graph* graph = new Graph();
graph->V = V;
graph->E = E;
graph->edge = new Edge[graph->E * sizeof(Edge)];
return graph;
}
// A utility function to find the subset of an element i
int find(int parent[], int i)
{
if (parent[i] == i)
return i;
return find(parent, parent[i]);
}
// A utility function to do union of two subsets
void Union(int parent[], int x, int y) { parent[x] = y; }
// The main function to check whether a given graph contains
// cycle or not
int isCycle(Graph* graph)
{
// Allocate memory for creating V subsets
int* parent = new int[graph->V];
// Initialize all subsets as single element sets
for(int i = 0; i < graph->V; i++) {
parent[i] = i;
}
// Iterate through all edges of graph, find subset of
// both vertices of every edge, if both subsets are
// same, then there is cycle in graph.
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;
}
// Driver code
int main()
{
/* Let us create the following graph
0
| \
| \
1---2 */
int V = 3, E = 3;
Graph* graph = createGraph(V, E);
// add edge 0-1
graph->edge[0].src = 0;
graph->edge[0].dest = 1;
// add edge 1-2
graph->edge[1].src = 1;
graph->edge[1].dest = 2;
// add edge 0-2
graph->edge[2].src = 0;
graph->edge[2].dest = 2;
if (isCycle(graph))
cout << "Graph contains cycle";
else
cout << "Graph doesn't contain cycle";
return 0;
}
// This code is contributed by rathbhupendra
Graph contains cycle
请注意， union()和find()的实现是天真的，在最坏的情况下需要O(n) 时间。使用按等级或高度联合，可以将这些方法改进为 O(logN)。