經典算法之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 /// <summary>
3 /// 矩陣的構建
4 /// </summary>
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<Edge>();
40
41 //并查集
42 set = new DisjointSet<int>(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 #endregion2：Kruskal算法
并查集，優先隊列都有數據了，下面我們只要出隊操作就行了，如果邊的頂點不在一個集合中，我們將其收集作為最小生成樹的一條邊，
按著這樣的方式，最終生成樹構建完畢，怎么樣，組合拳打的爽不爽？
1 #region Kruskal算法
2 /// <summary>
3 /// Kruskal算法
4 /// </summary>
5 public List<Edge> Kruskal()
6 {
7 //最后收集到的最小生成樹的邊
8 List<Edge> list = new List<Edge>();
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最后是總的代碼：
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 using System.Threading.Tasks;
9
10 namespace ConsoleApplication2
11 {
12 public class Program
13 {
14 public static void Main()
15 {
16 MatrixGraph graph = new MatrixGraph();
17
18 graph.Build();
19
20 var edges = graph.Kruskal();
21
22 foreach (var edge in edges)
23 {
24 Console.WriteLine("({0},{1})({2})", edge.startEdge, edge.endEdge, edge.weight);
25 }
26
27 Console.Read();
28 }
29 }
30
31 #region 定義矩陣節點
32 /// <summary>
33 /// 定義矩陣節點
34 /// </summary>
35 public class MatrixGraph
36 {
37 Graph graph = new Graph();
38
39 PriorityQueue<Edge> queue;
40
41 DisjointSet<int> set;
42
43 public class Graph
44 {
45 /// <summary>
46 /// 頂點信息
47 /// </summary>
48 public int[] vertexs;
49
50 /// <summary>
51 /// 邊的條數
52 /// </summary>
53 public int[,] edges;
54
55 /// <summary>
56 /// 頂點個數
57 /// </summary>
58 public int vertexsNum;
59
60 /// <summary>
61 /// 邊的個數
62 /// </summary>
63 public int edgesNum;
64 }
65
66 #region 矩陣的構建
67 /// <summary>
68 /// 矩陣的構建
69 /// </summary>
70 public void Build()
71 {
72 //頂點數
73 graph.vertexsNum = 6;
74
75 //邊數
76 graph.edgesNum = 8;
77
78 graph.vertexs = new int[graph.vertexsNum];
79
80 graph.edges = new int[graph.vertexsNum, graph.vertexsNum];
81
82 //構建二維數組
83 for (int i = 0; i < graph.vertexsNum; i++)
84 {
85 //頂點
86 graph.vertexs[i] = i;
87
88 for (int j = 0; j < graph.vertexsNum; j++)
89 {
90 graph.edges[i, j] = int.MaxValue;
91 }
92 }
93
94 graph.edges[0, 1] = graph.edges[1, 0] = 80;
95 graph.edges[0, 3] = graph.edges[3, 0] = 100;
96 graph.edges[0, 5] = graph.edges[5, 0] = 20;
97 graph.edges[1, 2] = graph.edges[2, 1] = 90;
98 graph.edges[2, 5] = graph.edges[5, 2] = 70;
99 graph.edges[4, 5] = graph.edges[5, 4] = 40;
100 graph.edges[3, 4] = graph.edges[4, 3] = 60;
101 graph.edges[2, 3] = graph.edges[3, 2] = 10;
102
103 //優先隊列，存放樹中的邊
104 queue = new PriorityQueue<Edge>();
105
106 //并查集
107 set = new DisjointSet<int>(graph.vertexs);
108
109 //將對角線讀入到優先隊列
110 for (int i = 0; i < graph.vertexsNum; i++)
111 {
112 for (int j = i; j < graph.vertexsNum; j++)
113 {
114 //說明該邊有權重
115 if (graph.edges[i, j] != int.MaxValue)
116 {
117 queue.Eequeue(new Edge()
118 {
119 startEdge = i,
120 endEdge = j,
121 weight = graph.edges[i, j]
122 }, graph.edges[i, j]);
123 }
124 }
125 }
126 }
127 #endregion
128
129 #region 邊的信息
130 /// <summary>
131 /// 邊的信息
132 /// </summary>
133 public class Edge
134 {
135 //開始邊
136 public int startEdge;
137
138 //結束邊
139 public int endEdge;
140
141 //權重
142 public int weight;
143 }
144 #endregion
145
146 #region Kruskal算法
147 /// <summary>
148 /// Kruskal算法
149 /// </summary>
150 public List<Edge> Kruskal()
151 {
152 //最后收集到的最小生成樹的邊
153 List<Edge> list = new List<Edge>();
154
155 //循環隊列
156 while (queue.Count() > 0)
157 {
158 var edge = queue.Dequeue();
159
160 //如果該兩點是同一個集合，則剔除該集合
161 if (set.IsSameSet(edge.t.startEdge, edge.t.endEdge))
162 continue;
163
164 list.Add(edge.t);
165
166 //然后將startEdge 和 endEdge Union起來，表示一個集合
167 set.Union(edge.t.startEdge, edge.t.endEdge);
168
169 //如果n個節點有n-1邊的時候，此時生成樹已經構建完畢，提前退出
170 if (list.Count == graph.vertexsNum - 1)
171 break;
172 }
173
174 return list;
175 }
176 #endregion
177 }
178 #endregion
179 }
