经典算法题每日演练——第十四题Prim算法

图论在数据结构中是⾮常有趣⽽复杂的，作为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 ///

6 public char[] vertexs; 7

8 ///

13 ///

16 public int vertexsNum;17

18 ///

21 public int edgesNum;22 }

2：矩阵构建

矩阵构建很简单，这⾥把上图中的顶点和权的信息保存在矩阵中。

1 #region 矩阵的构建 2 ///

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 ///

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 = end47 };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].endEdge75 });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})\14 }15

16 Console.Read();17 }

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 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 ///

37 public class MatrixGraph 38 {

39 Graph graph = new Graph(); 40

41 public class Graph 42 {

43 ///

46 public char[] vertexs; 47

48 ///

53 ///

56 public int vertexsNum; 57

58 ///

61 public int edgesNum; 62 } 63

64 #region 矩阵的构建 65 ///

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 #endregion103

104 #region 边的信息105 ///

110 //开始边

111 public char startEdge;112

113 //结束边

114 public char endEdge;

115

116 //权重

117 public int weight;118 }

119 #endregion120

121 #region prim算法122 ///

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 = end167 };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].endEdge195 });196 }197 }

198 return outputDic;

199 }

200 #endregion201 }202 }