图论在资料结构中是非常有趣而复杂的，作为 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