經典演演算法題每日演練——第十六題 Kruskal 演演算法

這篇我們看看第二種生成樹的 Kruskal 演演算法，這個演演算法的魅力在於我們可以打一下演演算法和資料結構的組合拳，很有意思的。
一：思想
若存在 M={0,1,2,3,4,5} 這樣 6 個節點，我們知道 Prim 演演算法構建生成樹是從” 頂點” 這個角度來思考的，然後採用 “貪心思想”
來一步步擴大化，最後形成整體最優解，而 Kruskal 演演算法有點意思，它是站在” 邊 “這個角度在思考的，首先我有兩個集合。
1. 頂點集合 (vertexs)：
比如 M 集合中的每個元素都可以認為是一個獨根樹（是不是想到了並查集？）。
2. 邊集合 (edges)：
對圖中的每條邊按照權值大小進行排序。（是不是想到了優先佇列？）
好了，下面該如何操作呢？
首先：我們從 edges 中選出權值最小的一條邊來作為生成樹的一條邊，然後將該邊的兩個頂點合併為一個新的樹。
然後：我們繼續從 edges 中選出次小的邊作為生成樹的第二條邊，但是前提就是邊的兩個頂點一定是屬於兩個集合中，如果不是
則剔除該邊繼續選下一條次小邊。
最後：經過反覆操作，當我們發現 n 個頂點的圖中生成樹已經有 n-1 邊的時候，此時生成樹構建完畢。

從圖中我們還是很清楚的看到 Kruskal 演演算法構建生成樹的詳細過程，同時我們也看到了” 並查集 “和 “優先佇列 “這兩個神器
來加速我們的生成樹構建。
 
二：構建
1.Build 方法
這裡我灌的是一些測試資料，同時在矩陣構建完畢後，將頂點資訊放入並查集，同時將邊的資訊放入優先佇列，方便我們在
做生成樹的時候秒殺。

1 #region 矩陣的構建
2 ///

3 /// 矩陣的構建
4 ///

5 public void Build()
6 {
7 //頂點數
8 graph.vertexsNum = 6;
9
10 //邊數
11 graph.edgesNum = 8;
12
13 graph.vertexs = new int[graph.vertexsNum];
14
15 graph.edges = new int[graph.vertexsNum, graph.vertexsNum];
16
17 //構建二維陣列
18 for (int i = 0; i < graph.vertexsNum; i++) 19 { 20 //頂點 21 graph.vertexs[i] = i; 22 23 for (int j = 0; j < graph.vertexsNum; j++) 24 { 25 graph.edges[i, j] = int.MaxValue; 26 } 27 } 28 29 graph.edges[0, 1] = graph.edges[1, 0] = 80; 30 graph.edges[0, 3] = graph.edges[3, 0] = 100; 31 graph.edges[0, 5] = graph.edges[5, 0] = 20; 32 graph.edges[1, 2] = graph.edges[2, 1] = 90; 33 graph.edges[2, 5] = graph.edges[5, 2] = 70; 34 graph.edges[4, 5] = graph.edges[5, 4] = 40; 35 graph.edges[3, 4] = graph.edges[4, 3] = 60; 36 graph.edges[2, 3] = graph.edges[3, 2] = 10; 37 38 //優先佇列，存放樹中的邊 39 queue = new PriorityQueue();
40
41 //並查集
42 set = new DisjointSet(graph.vertexs);
43
44 //將對角線讀入到優先佇列
45 for (int i = 0; i < graph.vertexsNum; i++) 46 { 47 for (int j = i; j < graph.vertexsNum; j++) 48 { 49 //說明該邊有權重 50 if (graph.edges[i, j] != int.MaxValue) 51 { 52 queue.Eequeue(new Edge() 53 { 54 startEdge = i, 55 endEdge = j, 56 weight = graph.edges[i, j] 57 }, graph.edges[i, j]); 58 } 59 } 60 } 61 } 62 #endregion   2：Kruskal 演演算法 並查集，優先佇列都有資料了，下面我們只要出隊操作就行了，如果邊的頂點不在一個集合中，我們將其收集作為最小生成樹的一條邊， 按著這樣的方式，最終生成樹構建完畢，怎麼樣，組合拳打的爽不爽？ 1 #region Kruskal 演演算法 2 ///

3 /// Kruskal 演演算法
4 ///

5 public List Kruskal()
6 {
7 //最後收集到的最小生成樹的邊
8 List list = new List();
9
10 //迴圈佇列
11 while (queue.Count() > 0)
12 {
13 var edge = queue.Dequeue();
14
15 //如果該兩點是同一個集合，則剔除該集合
16 if (set.IsSameSet(edge.t.startEdge, edge.t.endEdge))
17 continue;
18
19 list.Add(edge.t);
20
21 //然後將 startEdge 和 endEdge Union 起來，表示一個集合
22 set.Union(edge.t.startEdge, edge.t.endEdge);
23
24 //如果 n 個節點有 n-1 邊的時候，此時生成樹已經構建完畢，提前退出
25 if (list.Count == graph.vertexsNum – 1)
26 break;
27 }
28
29 return list;
30 }
31 #endregion

最後是總的程式碼：
View Code
並查集：

View Code

1 using System;
2 using System.Collections.Generic;
3 using System.Linq;
4 using System.Text;
5
6 namespace ConsoleApplication2
7 {
8 ///

9 /// 並查集
10 ///

11 public class DisjointSet where T : IComparable
12 {
13 #region 樹節點
14 ///

15 /// 樹節點
16 ///

17 public class Node
18 {
19 ///

20 /// 父節點
21 ///

22 public T parent;
23
24 ///

25 /// 節點的秩
26 ///

27 public int rank;
28 }
29 #endregion
30
31 Dictionary dic = new Dictionary();
32
33 public DisjointSet(T[] c)
34 {
35 Init(c);
36 }
37
38 #region 做單一集合的初始化操作
39 ///

40 /// 做單一集合的初始化操作
41 ///

42 public void Init(T[] c)
43 {
44 //預設的不想交集合的父節點指向自己
45 for (int i = 0; i < c.Length; i++) 46 { 47 dic.Add(c[i], new Node() 48 { 49 parent = c[i], 50 rank = 0 51 }); 52 } 53 } 54 #endregion 55 56 #region 判斷兩元素是否屬於同一個集合 57 ///

58 /// 判斷兩元素是否屬於同一個集合
59 ///

60 /// 61 /// 62 ///
63 public bool IsSameSet(T root1, T root2)
64 {
65 return Find(root1).CompareTo(Find(root2)) == 0;
66 }
67 #endregion
68
69 #region 查詢 x 所屬的集合
70 ///

71 /// 查詢 x 所屬的集合
72 ///

73 /// 74 ///
75 public T Find(T x)
76 {
77 //如果相等，則說明已經到根節點了，返回根節點元素
78 if (dic[x].parent.CompareTo(x) == 0)
79 return x;
80
81 //路徑壓縮 (回溯的時候賦值，最終的值就是上面返回的”x”，也就是一條路徑上全部被修改了)
82 return dic[x].parent = Find(dic[x].parent);
83 }
84 #endregion
85
86 #region 合併兩個不相交集合
87 ///

88 /// 合併兩個不相交集合
89 ///

90 /// 91 /// 92 ///
93 public void Union(T root1, T root2)
94 {
95 T x1 = Find(root1);
96 T y1 = Find(root2);
97
98 //如果根節點相同則說明是同一個集合
99 if (x1.CompareTo(y1) == 0)
100 return;
101
102 //說明左集合的深度 < 右集合 103 if (dic[x1].rank < dic[y1].rank) 104 { 105 //將左集合指向右集合 106 dic[x1].parent = y1; 107 } 108 else 109 { 110 //如果 秩 相等，則將 y1 併入到 x1 中，並將 x1++ 111 if (dic[x1].rank == dic[y1].rank) 112 dic[x1].rank++; 113 114 dic[y1].parent = x1; 115 } 116 } 117 #endregion 118 } 119 } 優先佇列： View Code 1 using System; 2 using System.Collections.Generic; 3 using System.Linq; 4 using System.Text; 5 using System.Diagnostics; 6 using System.Threading; 7 using System.IO; 8 9 namespace ConsoleApplication2 10 { 11 public class PriorityQueue where T : class
12 {
13 ///

14 /// 定義一個陣列來存放節點
15 ///

16 private List nodeList = new List();
17
18 #region 堆節點定義
19 ///

20 /// 堆節點定義
21 ///

22 public class HeapNode
23 {
24 ///

25 /// 實體資料
26 ///

27 public T t { get; set; }
28
29 ///

30 /// 優先順序別 1-10 個級別 (優先順序別遞增)
31 ///

32 public int level { get; set; }
33
34 public HeapNode(T t, int level)
35 {
36 this.t = t;
37 this.level = level;
38 }
39
40 public HeapNode() { }
41 }
42 #endregion
43
44 #region 新增操作
45 ///

46 /// 新增操作
47 ///

48 public void Eequeue(T t, int level = 1)
49 {
50 //將當前節點追加到堆尾
51 nodeList.Add(new HeapNode(t, level));
52
53 //如果只有一個節點，則不需要進行篩操作
54 if (nodeList.Count == 1)
55 return;
56
57 //獲取最後一個非葉子節點
58 int parent = nodeList.Count / 2 – 1;
59
60 //堆調整
61 UpHeapAdjust(nodeList, parent);
62 }
63 #endregion
64
65 #region 對堆進行上濾操作，使得滿足堆性質
66 ///

67 /// 對堆進行上濾操作，使得滿足堆性質
68 ///

69 /// 70 /// 非葉子節點的之後指標（這裡要注意：我們
71 /// 的篩操作時針對非葉節點的）
72 /// 73 public void UpHeapAdjust(List nodeList, int parent)
74 {
75 while (parent >= 0)
76 {
77 //當前 index 節點的左孩子
78 var left = 2 * parent + 1;
79
80 //當前 index 節點的右孩子
81 var right = left + 1;
82
83 //parent 子節點中最大的孩子節點，方便於 parent 進行比較
84 //預設為 left 節點
85 var min = left;
86
87 //判斷當前節點是否有右孩子
88 if (right < nodeList.Count) 89 { 90 //判斷 parent 要比較的最大子節點 91 min = nodeList[left].level < nodeList[right].level ? left : right; 92 } 93 94 //如果parent節點大於它的某個子節點的話，此時篩操作 95 if (nodeList[parent].level > nodeList[min].level)
96 {
97 //子節點和父節點進行交換操作
98 var temp = nodeList[parent];
99 nodeList[parent] = nodeList[min];
100 nodeList[min] = temp;
101
102 //繼續進行更上一層的過濾
103 parent = (int)Math.Ceiling(parent / 2d) – 1;
104 }
105 else
106 {
107 break;
108 }
109 }
110 }
111 #endregion
112
113 #region 優先佇列的出隊操作
114 ///

115 /// 優先佇列的出隊操作
116 ///

117 ///
118 public HeapNode Dequeue()
119 {
120 if (nodeList.Count == 0)
121 return null;
122
123 //出佇列操作，彈出資料頭元素
124 var pop = nodeList[0];
125
126 //用尾元素填充頭元素
127 nodeList[0] = nodeList[nodeList.Count – 1];
128
129 //刪除尾節點
130 nodeList.RemoveAt(nodeList.Count – 1);
131
132 //然後從根節點下濾堆
133 DownHeapAdjust(nodeList, 0);
134
135 return pop;
136 }
137 #endregion
138
139 #region 對堆進行下濾操作，使得滿足堆性質
140 ///

141 /// 對堆進行下濾操作，使得滿足堆性質
142 ///

143 /// 144 /// 非葉子節點的之後指標（這裡要注意：我們
145 /// 的篩操作時針對非葉節點的）
146 /// 147 public void DownHeapAdjust(List nodeList, int parent)
148 {
149 while (2 * parent + 1 < nodeList.Count) 150 { 151 //當前 index 節點的左孩子 152 var left = 2 * parent + 1; 153 154 //當前 index 節點的右孩子 155 var right = left + 1; 156 157 //parent 子節點中最大的孩子節點，方便於 parent 進行比較 158 //預設為 left 節點 159 var min = left; 160 161 //判斷當前節點是否有右孩子 162 if (right < nodeList.Count) 163 { 164 //判斷 parent 要比較的最大子節點 165 min = nodeList[left].level < nodeList[right].level ? left : right; 166 } 167 168 //如果parent節點小於它的某個子節點的話，此時篩操作 169 if (nodeList[parent].level > nodeList[min].level)
170 {
171 //子節點和父節點進行交換操作
172 var temp = nodeList[parent];
173 nodeList[parent] = nodeList[min];
174 nodeList[min] = temp;
175
176 //繼續進行更下一層的過濾
177 parent = min;
178 }
179 else
180 {
181 break;
182 }
183 }
184 }
185 #endregion
186
187 #region 獲取元素並下降到指定的 level 級別
188 ///

189 /// 獲取元素並下降到指定的 level 級別
190 ///

191 ///
192 public HeapNode GetAndDownPriority(int level)
193 {
194 if (nodeList.Count == 0)
195 return null;
196
197 //獲取頭元素
198 var pop = nodeList[0];
199
200 //設定指定優先順序（如果為 MinValue 則為 — 操作）
201 nodeList[0].level = level == int.MinValue ? –nodeList[0].level : level;
202
203 //下濾堆
204 DownHeapAdjust(nodeList, 0);
205
206 return nodeList[0];
207 }
208 #endregion
209
210 #region 獲取元素並下降優先順序
211 ///

212 /// 獲取元素並下降優先順序
213 ///

214 ///
215 public HeapNode GetAndDownPriority()
216 {
217 //下降一個優先順序
218 return GetAndDownPriority(int.MinValue);
219 }
220 #endregion
221
222 #region 返回當前優先佇列中的元素個數
223 ///

224 /// 返回當前優先佇列中的元素個數
225 ///

226 ///
227 public int Count()
228 {
229 return nodeList.Count;
230 }
231 #endregion
232 }
233 }

文章來自網際網路部落格網站：http://www.cnblogs.com/huangxincheng/archive/2012/12/17/2821132.html，版權歸作者所有。