Kruskal 最小生成樹算法
原文 http://www.cnblogs.com/gaochundong/p/kruskal_minimum_spanning_tree.html
對于一個給定的連通的無向圖 G = (V, E)，希望找到一個無回路的子集 T，T 是 E 的子集，它連接了所有的頂點，且其權值之和為最小。
因為 T 無回路且連接所有的頂點，所以它必然是一棵樹，稱為生成樹（Spanning Tree），因為它生成了圖 G。顯然，由于樹 T 連接了所有的頂點，所以樹 T 有 V - 1 條邊。一張圖 G 可以有很多棵生成樹，而把確定權值最小的樹 T 的問題稱為 最小生成樹問題（Minimum Spanning Tree） 。術語 "最小生成樹" 實際上是 "最小權值生成樹" 的縮寫。
Kruskal 算法提供一種在 O(ElogV) 運行時間確定最小生成樹的方案。Kruskal 算法基于 貪心算法（Greedy Algorithm） 的思想進行設計，其選擇的 貪心策略 就是，每次都選擇權重最小的但未形成環路的邊加入到生成樹中。其算法結構如下：
- 將所有的邊按照權重非遞減排序；
- 選擇最小權重的邊，判斷是否其在當前的生成樹中形成了一個環路。如果環路沒有形成，則將該邊加入樹中，否則放棄。
- 重復步驟 2，直到有 V - 1 條邊在生成樹中。
上述步驟 2 中使用了Union-Find 算法來判斷是否存在環路。
例如，下面是一個無向連通圖 G。
圖 G 中包含 9 個頂點和 14 條邊，所以期待的最小生成樹應包含 (9 - 1) = 8 條邊。
首先對所有的邊按照權重的非遞減順序排序：
Weight Src Dest 1 7 6 2 8 2 2 6 5 4 0 1 4 2 5 6 8 6 7 2 3 7 7 8 8 0 7 8 1 2 9 3 4 10 5 4 11 1 7 14 3 5
然后從排序后的列表中選擇權重最小的邊。
1. 選擇邊 {7, 6}，無環路形成，包含在生成樹中。
2. 選擇邊 {8, 2}，無環路形成，包含在生成樹中。
3. 選擇邊 {6, 5}，無環路形成，包含在生成樹中。
4. 選擇邊 {0, 1}，無環路形成，包含在生成樹中。
5. 選擇邊 {2, 5}，無環路形成，包含在生成樹中。
6. 選擇邊 {8, 6}，有環路形成，放棄。
7. 選擇邊 {2, 3}，無環路形成，包含在生成樹中。
8. 選擇邊 {7, 8}，有環路形成，放棄。
9. 選擇邊 {0, 7}，無環路形成，包含在生成樹中。
10. 選擇邊 {1, 2}，有環路形成，放棄。
11. 選擇邊 {3, 4}，無環路形成，包含在生成樹中。
12. 由于當前生成樹中已經包含 V - 1 條邊，算法結束。
C# 實現的 Kruskal 算法如下。
using System;
using System.Collections.Generic;
using System.Linq;
namespace GraphAlgorithmTesting
{
class Program
{
static void Main(string[] args)
{
Graph g = new Graph(9);
g.AddEdge(0, 1, 4);
g.AddEdge(0, 7, 8);
g.AddEdge(1, 2, 8);
g.AddEdge(1, 7, 11);
g.AddEdge(2, 3, 7);
g.AddEdge(2, 5, 4);
g.AddEdge(8, 2, 2);
g.AddEdge(3, 4, 9);
g.AddEdge(3, 5, 14);
g.AddEdge(5, 4, 10);
g.AddEdge(6, 5, 2);
g.AddEdge(8, 6, 6);
g.AddEdge(7, 6, 1);
g.AddEdge(7, 8, 7);
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.WriteLine();
Edge[] mst = g.Kruskal();
Console.WriteLine("MST Edges:");
foreach (var edge in mst)
{
Console.WriteLine("\t{0}", edge);
}
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 Subset
{
public int Parent { get; set; }
public int Rank { get; set; }
}
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(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;
}
private void Union(Subset[] subsets, int x, int y)
{
int xroot = Find(subsets, x);
int yroot = Find(subsets, y);
// Attach smaller rank tree under root of high rank tree
// (Union by Rank)
if (subsets[xroot].Rank < subsets[yroot].Rank)
subsets[xroot].Parent = yroot;
else if (subsets[xroot].Rank > subsets[yroot].Rank)
subsets[yroot].Parent = xroot;
// If ranks are same, then make one as root and increment
// its rank by one
else
{
subsets[yroot].Parent = xroot;
subsets[xroot].Rank++;
}
}
public bool HasCycle()
{
Subset[] subsets = new Subset[VertexCount];
for (int i = 0; i < subsets.Length; i++)
{
subsets[i] = new Subset();
subsets[i].Parent = i;
subsets[i].Rank = 0;
}
// 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(subsets, edge.Begin);
int y = Find(subsets, edge.End);
if (x == y)
{
return true;
}
Union(subsets, x, y);
}
return false;
}
public Edge[] Kruskal()
{
// This will store the resultant MST
Edge[] mst = new Edge[VertexCount - 1];
// Step 1: Sort all the edges in non-decreasing order of their weight
// If we are not allowed to change the given graph, we can create a copy of
// array of edges
var sortedEdges = this.Edges.OrderBy(t => t.Weight);
var enumerator = sortedEdges.GetEnumerator();
// Allocate memory for creating V ssubsets
// Create V subsets with single elements
Subset[] subsets = new Subset[VertexCount];
for (int i = 0; i < subsets.Length; i++)
{
subsets[i] = new Subset();
subsets[i].Parent = i;
subsets[i].Rank = 0;
}
// Number of edges to be taken is equal to V-1
int e = 0;
while (e < VertexCount - 1)
{
// Step 2: Pick the smallest edge. And increment the index
// for next iteration
Edge nextEdge;
if (enumerator.MoveNext())
{
nextEdge = enumerator.Current;
int x = Find(subsets, nextEdge.Begin);
int y = Find(subsets, nextEdge.End);
// If including this edge does't cause cycle, include it
// in result and increment the index of result for next edge
if (x != y)
{
mst[e++] = nextEdge;
Union(subsets, x, y);
}
else
{
// Else discard the nextEdge
}
}
}
return mst;
}
}
}
}輸出結果如下：
參考資料
本文由用戶 jopen 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。
轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。
本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！