不相交集合数据结构（Disjoint-set data structure）是一种用于跟踪集合被分割成多个不相交的子集合的数据结构，每个集合通过一个代表来标识，代表即集合中的某个成员。
Union-Find 算法为该数据结构提供了两种非常有用的操作：
- Find：判断子集中是否存在特定的元素。可以用于检测是否两个元素存在于相同的子集中。
- Union：将两个不子集合并成新的子集合。
Union-Find 算法的一个具体的应用就是在无向图（Undirected Graph）中检测是否存在环路（Cycle）。
例如，下面这张无向图 G：
0| \| \1-----2
G 中包含 3 个顶点和 3 条边 { {0, 1}, {1, 2}, {2, 1}}。
初始时，设 int[] parent = new int[VertexCount]，默认每个顶点的子集中只有自己，设为 -1。
0 1 2-1 -1 -1
处理边 {0, 1}，Find 顶点 0 和 1 的子集，发现它们在不同的子集中，则 Union 它们，此时 1 代表了子集 {0, 1}。
0 1 21 -1 -1
处理边 {1, 2}，Find 顶点 1 和 2 的子集，发现它们在不同的子集中，则 Union 它们，此时 2 代表了子集 {0, 1, 2}。
0 1 21 2 -1
处理边 {2, 1}，Find 顶点 2 和 1 的子集，发现它们在相同的子集中，则图存在环。
简单实现如下，其时间复杂度为 O(n)。
1 using System; 2 using System.Collections.Generic; 3 using System.Linq; 4 5 namespace GraphAlgorithmTesting 6 { 7 class Program 8 { 9 static void Main(string[] args) 10 { 11 Graph g = new Graph(6); 12 g.AddEdge(0, 1, 16); 13 g.AddEdge(0, 2, 13); 14 g.AddEdge(1, 2, 10); 15 g.AddEdge(1, 3, 12); 16 //g.AddEdge(2, 1, 4); 17 g.AddEdge(2, 4, 14); 18 //g.AddEdge(3, 2, 9); 19 g.AddEdge(3, 5, 20); 20 //g.AddEdge(4, 3, 7); 21 //g.AddEdge(4, 5, 4); 22 23 Console.WriteLine(); 24 Console.WriteLine("Graph Vertex Count : {0}", g.VertexCount); 25 Console.WriteLine("Graph Edge Count : {0}", g.EdgeCount); 26 Console.WriteLine(); 27 28 Console.WriteLine("Is there cycle in graph: {0}", g.HasCycle()); 29 30 Console.ReadKey(); 31 } 32 33 class Edge 34 { 35 public Edge(int begin, int end, int weight) 36 { 37 this.Begin = begin; 38 this.End = end; 39 this.Weight = weight; 40 } 41 42 public int Begin { get; private set; } 43 public int End { get; private set; } 44 public int Weight { get; private set; } 45 46 public override string ToString() 47 { 48 return string.Format( 49 "Begin[{0}], End[{1}], Weight[{2}]", 50 Begin, End, Weight); 51 } 52 } 53 54 class Graph 55 { 56 private Dictionary > _adjacentEdges 57 = new Dictionary >(); 58 59 public Graph(int vertexCount) 60 { 61 this.VertexCount = vertexCount; 62 } 63 64 public int VertexCount { get; private set; } 65 66 public IEnumerable Vertices { get { return _adjacentEdges.Keys; } } 67 68 public IEnumerable Edges 69 { 70 get { return _adjacentEdges.Values.SelectMany(e => e); } 71 } 72 73 public int EdgeCount { get { return this.Edges.Count(); } } 74 75 public void AddEdge(int begin, int end, int weight) 76 { 77 if (!_adjacentEdges.ContainsKey(begin)) 78 { 79 var edges = new List (); 80 _adjacentEdges.Add(begin, edges); 81 } 82 83 _adjacentEdges[begin].Add(new Edge(begin, end, weight)); 84 } 85 86 private int Find(int[] parent, int i) 87 { 88 if (parent[i] == -1) 89 return i; 90 return Find(parent, parent[i]); 91 } 92 93 private void Union(int[] parent, int x, int y) 94 { 95 int xset = Find(parent, x); 96 int yset = Find(parent, y); 97 parent[xset] = yset; 98 } 99 100 public bool HasCycle()101 {102 int[] parent = new int[VertexCount];103 for (int i = 0; i < parent.Length; i++)104 {105 parent[i] = -1;106 }107 108 // Iterate through all edges of graph, find subset of both109 // vertices of every edge, if both subsets are same, 110 // then there is cycle in graph.111 foreach (var edge in this.Edges)112 {113 int x = Find(parent, edge.Begin);114 int y = Find(parent, edge.End);115 116 if (x == y)117 {118 return true;119 }120 121 Union(parent, x, y);122 }123 124 return false;125 }126 }127 }128 } 本篇文章《》由 发表自，未经作者本人同意禁止任何形式的转载，任何自动或人为的爬虫转载行为均为耍流氓。