Union-Find 检测无向图有无环路算法

不相交集合数据结构（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  2

1 -1 -1

处理边 {1, 2}，Find 顶点 1 和 2 的子集，发现它们在不同的子集中，则 Union 它们，此时 2 代表了子集 {0, 1, 2}。

0 1  2

1 2 -1

处理边 {2, 1}，Find 顶点 2 和 1 的子集，发现它们在相同的子集中，则图存在环。

Union-Find 算法简单实现如下，其时间复杂度为 O(n)。

 using System;

 using System.Collections.Generic;

 using System.Linq;

 namespace GraphAlgorithmTesting

 {

   class Program

   {

     static void Main(string[] args)

     {

       Graph g = new Graph();

       g.AddEdge(, , );

       g.AddEdge(, , );

       g.AddEdge(, , );

       g.AddEdge(, , );

       //g.AddEdge(2, 1, 4);

       g.AddEdge(, , );

       //g.AddEdge(3, 2, 9);

       g.AddEdge(, , );

       //g.AddEdge(4, 3, 7);

       //g.AddEdge(4, 5, 4);

       Console.WriteLine();

       Console.WriteLine("Graph Vertex Count : {0}", g.VertexCount);

       Console.WriteLine("Graph Edge Count : {0}", g.EdgeCount);

       Console.WriteLine();

       Console.WriteLine("Is there cycle in graph: {0}", g.HasCycle());

       Console.ReadKey();

     }

     class Edge

     {

       public Edge(int begin, int end, int weight)

       {

         this.Begin = begin;

         this.End = end;

         this.Weight = weight;

       }

       public int Begin { get; private set; }

       public int End { get; private set; }

       public int Weight { get; private set; }

       public override string ToString()

       {

         return string.Format(

           "Begin[{0}], End[{1}], Weight[{2}]",

           Begin, End, Weight);

       }

     }

     class Graph

     {

       private Dictionary<int, List<Edge>> _adjacentEdges

         = new Dictionary<int, List<Edge>>();

       public Graph(int vertexCount)

       {

         this.VertexCount = vertexCount;

       }

       public int VertexCount { get; private set; }

       public IEnumerable<int> Vertices { get { return _adjacentEdges.Keys; } }

       public IEnumerable<Edge> Edges

       {

         get { return _adjacentEdges.Values.SelectMany(e => e); }

       }

       public int EdgeCount { get { return this.Edges.Count(); } }

       public void AddEdge(int begin, int end, int weight)

       {

         if (!_adjacentEdges.ContainsKey(begin))

         {

           var edges = new List<Edge>();

           _adjacentEdges.Add(begin, edges);

         }

         _adjacentEdges[begin].Add(new Edge(begin, end, weight));

       }

       private int Find(int[] parent, int i)

       {

         if (parent[i] == -)

           return i;

         return Find(parent, parent[i]);

       }

       private void Union(int[] parent, int x, int y)

       {

         int xset = Find(parent, x);

         int yset = Find(parent, y);

         parent[xset] = yset;

       }

       public bool HasCycle()

       {

         int[] parent = new int[VertexCount];

         for (int i = ; i < parent.Length; i++)

         {

           parent[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.

         foreach (var edge in this.Edges)

         {

           int x = Find(parent, edge.Begin);

           int y = Find(parent, edge.End);

           if (x == y)

           {

             return true;

           }

           Union(parent, x, y);

         }

         return false;

       }

     }

   }

 }

本篇文章《Union-Find 检测无向图有无环路算法》由 Dennis Gao 发表自博客园，未经作者本人同意禁止任何形式的转载，任何自动或人为的爬虫转载行为均为耍流氓。

巴特西

Union-Find 检测无向图有无环路算法

最新文章

热门文章