基于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}}