圖論在資料結構中是非常有趣而複雜的，作為 web 碼農的我，在實際開發中一直沒有找到它的使用場景，不像樹那樣的頻繁使用，不過還是準備
仔細的把圖論全部過一遍。
一：最小生成樹
圖中有一個好玩的東西叫做生成樹，就是用邊來把所有的頂點聯通起來，前提條件是最後形成的聯通圖中不能存在迴路，所以就形成這樣一個
推理：假設圖中的頂點有 n 個，則生成樹的邊有 n-1 條，多一條會存在迴路，少一路則不能把所有頂點聯通起來，如果非要在圖中加上權重，則生成樹
中權重最小的叫做最小生成樹。

對於上面這個帶權無向圖來説，它的生成樹有多個，同樣最小生成樹也有多個，因為我們比的是權重的大小。
 
二：Prim 演算法
求最小生成樹的演算法有很多，常用的是 Prim 演算法和 Kruskal 演算法，為了保證單一職責，我把 Kruskal 演算法放到下一篇，那麼 Prim 演算法的思想
是什麼呢？很簡單，貪心思想。
如上圖：現有集合 M={A,B,C,D,E,F}，再設集合 N={} 。
第一步：挑選任意節點（比如 A), 將其加入到 N 集合，同時剔除 M 集合的 A 。
第二步：尋找 A 節點權值最小的鄰節點（比如 F），然後將 F 加入到 N 集合，此時 N={A,F}，同時剔除 M 集合中的 F 。
第三步：尋找 {A,F} 中的權值最小的鄰節點（比如 E），然後將 E 加入到 N 集合，此時 N={A,F,E}，同時剔除 M 集合的 E 。
。。。
最後 M 集合為 {} 時，生成樹就構建完畢了，是不是非常的簡單，這種貪心做法我想大家都能想得到，如果演算法配合一個好的資料結構，就會
如虎添翼。
 
三：程式碼
1. 圖的儲存
圖的儲存有很多方式，鄰接矩陣，鄰接表，十字連結串列等等，當然都有自己的適合場景，下面用鄰接矩陣來玩玩，鄰接矩陣需要採用兩個陣列，
①. 儲存頂點資訊的一維陣列，
②. 儲存邊資訊的二維陣列。

1 public class Graph
2 {
3 ///

4 /// 頂點個數
5 ///

6 public char[] vertexs;
7
8 ///

9 /// 邊的條數
10 ///

11 public int[,] edges;
12
13 ///

14 /// 頂點個數
15 ///

16 public int vertexsNum;
17
18 ///

19 /// 邊的個數
20 ///

21 public int edgesNum;
22 }

 
2：矩陣構建
矩陣構建很簡單，這裏把上圖中的頂點和權的資訊儲存在矩陣中。

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 char[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] = (char)(i + 65); 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[3, 2] = graph.edges[2, 3] = 100; 35 graph.edges[4, 5] = graph.edges[5, 4] = 40; 36 graph.edges[3, 4] = graph.edges[4, 3] = 60; 37 graph.edges[2, 3] = graph.edges[3, 2] = 10; 38 } 39 #endregion   3：Prim 要玩 Prim，我們需要兩個字典。 ①：儲存當前節點的字典，其中包含該節點的起始邊和終邊以及權值，用 weight=-1 來記錄當前節點已經訪問過，用 weight=int.MaxValue 表示 兩節點沒有邊。 ②：輸出節點的字典，存放的就是我們的 N 集合。 當然這個複雜度玩高了, 為 O(N2)，尋找 N 集合的鄰邊最小權值時，我們可以玩玩 AVL 或者優先佇列來降低複雜度。 1 #region prim 演算法 2 ///

3 /// prim 演算法
4 ///

5 public Dictionary Prim()
6 {
7 Dictionary dic = new Dictionary();
8
9 //統計結果
10 Dictionary outputDic = new Dictionary();
11
12 //weight=MaxValue: 標識沒有邊
13 for (int i = 0; i < graph.vertexsNum; i++) 14 { 15 //起始邊 16 var startEdge = (char)(i + 65); 17 18 dic.Add(startEdge, new Edge() { weight = int.MaxValue }); 19 } 20 21 //取字元的開始位置 22 var index = 65; 23 24 //取當前要使用的字元 25 var start = (char)(index); 26 27 for (int i = 0; i < graph.vertexsNum; i++) 28 { 29 //標記開始邊已使用過 30 dic[start].weight = -1; 31 32 for (int j = 1; j < graph.vertexsNum; j++) 33 { 34 //獲取當前 c 的 鄰邊 35 var end = (char)(j + index); 36 37 //取當前字元的權重 38 var weight = graph.edges[(int)(start) - index, j]; 39 40 if (weight < dic[end].weight) 41 { 42 dic[end] = new Edge() 43 { 44 weight = weight, 45 startEdge = start, 46 endEdge = end 47 }; 48 } 49 } 50 51 var min = int.MaxValue; 52 53 char minkey = ' '; 54 55 foreach (var key in dic.Keys) 56 { 57 //取當前 最小的 key(使用過的除外) 58 if (min > dic[key].weight && dic[key].weight != -1)
59 {
60 min = dic[key].weight;
61 minkey = key;
62 }
63 }
64
65 start = minkey;
66
67 //邊為頂點減去 1
68 if (outputDic.Count < graph.vertexsNum - 1 && !outputDic.ContainsKey(minkey)) 69 { 70 outputDic.Add(minkey, new Edge() 71 { 72 weight = dic[minkey].weight, 73 startEdge = dic[minkey].startEdge, 74 endEdge = dic[minkey].endEdge 75 }); 76 } 77 } 78 return outputDic; 79 } 80 #endregion   4：最後我們來測試一下，看看找出的最小生成樹。 1 public static void Main() 2 { 3 MatrixGraph martix = new MatrixGraph(); 4 5 martix.Build(); 6 7 var dic = martix.Prim(); 8 9 Console.WriteLine("最小生成樹為："); 10 11 foreach (var key in dic.Keys) 12 { 13 Console.WriteLine("({0},{1})({2})", dic[key].startEdge, dic[key].endEdge, dic[key].weight); 14 } 15 16 Console.Read(); 17 }   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 SupportCenter.Test.ServiceReference2; 9 using System.Threading.Tasks; 10 11 namespace ConsoleApplication2 12 { 13 public class Program 14 { 15 public static void Main() 16 { 17 MatrixGraph martix = new MatrixGraph(); 18 19 martix.Build(); 20 21 var dic = martix.Prim(); 22 23 Console.WriteLine("最小生成樹為："); 24 25 foreach (var key in dic.Keys) 26 { 27 Console.WriteLine("({0},{1})({2})", dic[key].startEdge, dic[key].endEdge, dic[key].weight); 28 } 29 30 Console.Read(); 31 } 32 } 33 34 ///

35 /// 定義矩陣節點
36 ///

37 public class MatrixGraph
38 {
39 Graph graph = new Graph();
40
41 public class Graph
42 {
43 ///

44 /// 頂點個數
45 ///

46 public char[] vertexs;
47
48 ///

49 /// 邊的條數
50 ///

51 public int[,] edges;
52
53 ///

54 /// 頂點個數
55 ///

56 public int vertexsNum;
57
58 ///

59 /// 邊的個數
60 ///

61 public int edgesNum;
62 }
63
64 #region 矩陣的構建
65 ///

66 /// 矩陣的構建
67 ///

68 public void Build()
69 {
70 //頂點數
71 graph.vertexsNum = 6;
72
73 //邊數
74 graph.edgesNum = 8;
75
76 graph.vertexs = new char[graph.vertexsNum];
77
78 graph.edges = new int[graph.vertexsNum, graph.vertexsNum];
79
80 //構建二維陣列
81 for (int i = 0; i < graph.vertexsNum; i++) 82 { 83 //頂點 84 graph.vertexs[i] = (char)(i + 65); 85 86 for (int j = 0; j < graph.vertexsNum; j++) 87 { 88 graph.edges[i, j] = int.MaxValue; 89 } 90 } 91 92 graph.edges[0, 1] = graph.edges[1, 0] = 80; 93 graph.edges[0, 3] = graph.edges[3, 0] = 100; 94 graph.edges[0, 5] = graph.edges[5, 0] = 20; 95 graph.edges[1, 2] = graph.edges[2, 1] = 90; 96 graph.edges[2, 5] = graph.edges[5, 2] = 70; 97 graph.edges[3, 2] = graph.edges[2, 3] = 100; 98 graph.edges[4, 5] = graph.edges[5, 4] = 40; 99 graph.edges[3, 4] = graph.edges[4, 3] = 60; 100 graph.edges[2, 3] = graph.edges[3, 2] = 10; 101 } 102 #endregion 103 104 #region 邊的資訊 105 ///

106 /// 邊的資訊
107 ///

108 public class Edge
109 {
110 //開始邊
111 public char startEdge;
112
113 //結束邊
114 public char endEdge;
115
116 //權重
117 public int weight;
118 }
119 #endregion
120
121 #region prim 演算法
122 ///

123 /// prim 演算法
124 ///

125 public Dictionary Prim()
126 {
127 Dictionary dic = new Dictionary();
128
129 //統計結果
130 Dictionary outputDic = new Dictionary();
131
132 //weight=MaxValue: 標識沒有邊
133 for (int i = 0; i < graph.vertexsNum; i++) 134 { 135 //起始邊 136 var startEdge = (char)(i + 65); 137 138 dic.Add(startEdge, new Edge() { weight = int.MaxValue }); 139 } 140 141 //取字元的開始位置 142 var index = 65; 143 144 //取當前要使用的字元 145 var start = (char)(index); 146 147 for (int i = 0; i < graph.vertexsNum; i++) 148 { 149 //標記開始邊已使用過 150 dic[start].weight = -1; 151 152 for (int j = 1; j < graph.vertexsNum; j++) 153 { 154 //獲取當前 c 的 鄰邊 155 var end = (char)(j + index); 156 157 //取當前字元的權重 158 var weight = graph.edges[(int)(start) - index, j]; 159 160 if (weight < dic[end].weight) 161 { 162 dic[end] = new Edge() 163 { 164 weight = weight, 165 startEdge = start, 166 endEdge = end 167 }; 168 } 169 } 170 171 var min = int.MaxValue; 172 173 char minkey = ' '; 174 175 foreach (var key in dic.Keys) 176 { 177 //取當前 最小的 key(使用過的除外) 178 if (min > dic[key].weight && dic[key].weight != -1)
179 {
180 min = dic[key].weight;
181 minkey = key;
182 }
183 }
184
185 start = minkey;
186
187 //邊為頂點減去 1
188 if (outputDic.Count < graph.vertexsNum - 1 && !outputDic.ContainsKey(minkey)) 189 { 190 outputDic.Add(minkey, new Edge() 191 { 192 weight = dic[minkey].weight, 193 startEdge = dic[minkey].startEdge, 194 endEdge = dic[minkey].endEdge 195 }); 196 } 197 } 198 return outputDic; 199 } 200 #endregion 201 } 202 } 文章來自互聯網博客網站，原文連結 http://www.cnblogs.com/huangxincheng/archive/2012/12/12/2815214.html