基于C#实现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、图的存储

图的存储有很多方式，邻接矩阵，邻接表，十字链表等等，当然都有自己的适合场景，下面用邻接矩阵来玩玩，邻接矩阵需要采用两个数组，
①. 保存顶点信息的一维数组，
②. 保存边信息的二维数组。

 public class Graph{/// <summary>/// 顶点个数/// </summary>public char[] vertexs;/// <summary>/// 边的条数/// </summary>public int[,] edges;/// <summary>/// 顶点个数/// </summary>public int vertexsNum;/// <summary>/// 边的个数/// </summary>public int edgesNum;}

2、矩阵构建

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

 #region 矩阵的构建/// <summary>/// 矩阵的构建/// </summary>public void Build(){//顶点数graph.vertexsNum = 6;//边数graph.edgesNum = 8;graph.vertexs = new char[graph.vertexsNum];graph.edges = new int[graph.vertexsNum, graph.vertexsNum];//构建二维数组for (int i = 0; i < graph.vertexsNum; i++){//顶点graph.vertexs[i] = (char)(i + 65);for (int j = 0; j < graph.vertexsNum; j++){graph.edges[i, j] = int.MaxValue;}}graph.edges[0, 1] = graph.edges[1, 0] = 80;graph.edges[0, 3] = graph.edges[3, 0] = 100;graph.edges[0, 5] = graph.edges[5, 0] = 20;graph.edges[1, 2] = graph.edges[2, 1] = 90;graph.edges[2, 5] = graph.edges[5, 2] = 70;graph.edges[3, 2] = graph.edges[2, 3] = 100;graph.edges[4, 5] = graph.edges[5, 4] = 40;graph.edges[3, 4] = graph.edges[4, 3] = 60;graph.edges[2, 3] = graph.edges[3, 2] = 10;}#endregion

3、Prim

要玩 Prim，我们需要两个字典。
①：保存当前节点的字典，其中包含该节点的起始边和终边以及权值，用 weight=-1 来记录当前节点已经访问过，用 weight=int.MaxValue 表示两节点没有边。
②：输出节点的字典，存放的就是我们的 N 集合。
当然这个复杂度玩高了,为 O(N2)，寻找 N 集合的邻边最小权值时，我们可以玩玩 AVL 或者优先队列来降低复杂度。

 #region prim算法/// <summary>/// prim算法/// </summary>public Dictionary<char, Edge> Prim(){Dictionary<char, Edge> dic = new Dictionary<char, Edge>();//统计结果Dictionary<char, Edge> outputDic = new Dictionary<char, Edge>();//weight=MaxValue:标识没有边for (int i = 0; i < graph.vertexsNum; i++){//起始边var startEdge = (char)(i + 65);dic.Add(startEdge, new Edge() { weight = int.MaxValue });}//取字符的开始位置var index = 65;//取当前要使用的字符var start = (char)(index);for (int i = 0; i < graph.vertexsNum; i++){//标记开始边已使用过dic[start].weight = -1;for (int j = 1; j < graph.vertexsNum; j++){//获取当前 c 的 邻边var end = (char)(j + index);//取当前字符的权重var weight = graph.edges[(int)(start) - index, j];if (weight < dic[end].weight){dic[end] = new Edge(){weight = weight,startEdge = start,endEdge = end};}}var min = int.MaxValue;char minkey = ' ';foreach (var key in dic.Keys){//取当前 最小的 key(使用过的除外)if (min > dic[key].weight && dic[key].weight != -1){min = dic[key].weight;minkey = key;}}start = minkey;//边为顶点减去1if (outputDic.Count < graph.vertexsNum - 1 && !outputDic.ContainsKey(minkey)){outputDic.Add(minkey, new Edge(){weight = dic[minkey].weight,startEdge = dic[minkey].startEdge,endEdge = dic[minkey].endEdge});}}return outputDic;}#endregion

4、最后我们来测试一下，看看找出的最小生成树。

 public static void Main(){MatrixGraph martix = new MatrixGraph();martix.Build();var dic = martix.Prim();Console.WriteLine("最小生成树为：");foreach (var key in dic.Keys){Console.WriteLine("({0},{1})({2})", dic[key].startEdge, dic[key].endEdge, dic[key].weight);}Console.Read();}

 using System;using System.Collections.Generic;using System.Linq;using System.Text;using System.Diagnostics;using System.Threading;using System.IO;using SupportCenter.Test.ServiceReference2;using System.Threading.Tasks;namespace ConsoleApplication2{public class Program{public static void Main(){MatrixGraph martix = new MatrixGraph();martix.Build();var dic = martix.Prim();Console.WriteLine("最小生成树为：");foreach (var key in dic.Keys){Console.WriteLine("({0},{1})({2})", dic[key].startEdge, dic[key].endEdge, dic[key].weight);}Console.Read();}}/// <summary>/// 定义矩阵节点/// </summary>public class MatrixGraph{Graph graph = new Graph();public class Graph{/// <summary>/// 顶点个数/// </summary>public char[] vertexs;/// <summary>/// 边的条数/// </summary>public int[,] edges;/// <summary>/// 顶点个数/// </summary>public int vertexsNum;/// <summary>/// 边的个数/// </summary>public int edgesNum;}#region 矩阵的构建/// <summary>/// 矩阵的构建/// </summary>public void Build(){//顶点数graph.vertexsNum = 6;//边数graph.edgesNum = 8;graph.vertexs = new char[graph.vertexsNum];graph.edges = new int[graph.vertexsNum, graph.vertexsNum];//构建二维数组for (int i = 0; i < graph.vertexsNum; i++){//顶点graph.vertexs[i] = (char)(i + 65);for (int j = 0; j < graph.vertexsNum; j++){graph.edges[i, j] = int.MaxValue;}}graph.edges[0, 1] = graph.edges[1, 0] = 80;graph.edges[0, 3] = graph.edges[3, 0] = 100;graph.edges[0, 5] = graph.edges[5, 0] = 20;graph.edges[1, 2] = graph.edges[2, 1] = 90;graph.edges[2, 5] = graph.edges[5, 2] = 70;graph.edges[3, 2] = graph.edges[2, 3] = 100;graph.edges[4, 5] = graph.edges[5, 4] = 40;graph.edges[3, 4] = graph.edges[4, 3] = 60;graph.edges[2, 3] = graph.edges[3, 2] = 10;}#endregion#region 边的信息/// <summary>/// 边的信息/// </summary>public class Edge{//开始边public char startEdge;//结束边public char endEdge;//权重public int weight;}#endregion#region prim算法/// <summary>/// prim算法/// </summary>public Dictionary<char, Edge> Prim(){Dictionary<char, Edge> dic = new Dictionary<char, Edge>();//统计结果Dictionary<char, Edge> outputDic = new Dictionary<char, Edge>();//weight=MaxValue:标识没有边for (int i = 0; i < graph.vertexsNum; i++){//起始边var startEdge = (char)(i + 65);dic.Add(startEdge, new Edge() { weight = int.MaxValue });}//取字符的开始位置var index = 65;//取当前要使用的字符var start = (char)(index);for (int i = 0; i < graph.vertexsNum; i++){//标记开始边已使用过dic[start].weight = -1;for (int j = 1; j < graph.vertexsNum; j++){//获取当前 c 的 邻边var end = (char)(j + index);//取当前字符的权重var weight = graph.edges[(int)(start) - index, j];if (weight < dic[end].weight){dic[end] = new Edge(){weight = weight,startEdge = start,endEdge = end};}}var min = int.MaxValue;char minkey = ' ';foreach (var key in dic.Keys){//取当前 最小的 key(使用过的除外)if (min > dic[key].weight && dic[key].weight != -1){min = dic[key].weight;minkey = key;}}start = minkey;//边为顶点减去1if (outputDic.Count < graph.vertexsNum - 1 && !outputDic.ContainsKey(minkey)){outputDic.Add(minkey, new Edge(){weight = dic[minkey].weight,startEdge = dic[minkey].startEdge,endEdge = dic[minkey].endEdge});}}return outputDic;}#endregion}}