图论在数据结构中是非常有趣而复杂的，作为web码农的我，在实际开发中一直没有找到它的使用场景，不像树那样的频繁使用，不过还是准备 仔细的把图论全部过一遍。

一：最小生成树

  1.     图中有一个好玩的东西叫做生成树，就是用边来把所有的顶点联通起来，前提条件是最后形成的联通图中不能存在回路，所以就形成这样一个

推理：假设图中的顶点有n个，则生成树的边有n-1条，多一条会存在回路，少一路则不能把所有顶点联通起来，如果非要在图中加上权重，则生成树

中权重最小的叫做最小生成树。

第十四题 Prim算法 - 图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. 图的存储

图的存储有很多方式，邻接矩阵，邻接表，十字链表等等，当然都有自己的适合场景，下面用邻接矩阵来玩玩，邻接矩阵需要采用两个数组，

①. 保存顶点信息的一维数组，

②. 保存边信息的二维数组。

2：矩阵构建

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

3：Prim

要玩Prim，我们需要两个字典。

①：保存当前节点的字典，其中包含该节点的起始边和终边以及权值，用weight=-1来记录当前节点已经访问过，用weight=int.MaxValue表示 

  1.    两节点没有边。

②：输出节点的字典，存放的就是我们的N集合。

当然这个复杂度玩高了,为O(N2)，寻找N集合的邻边最小权值时，我们可以玩玩AVL或者优先队列来降低复杂度。

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.         }

第十四题 Prim算法 - 图2 

  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.     /// <summary>
  35.     /// 定义矩阵节点
  36.     /// </summary>
  37.     public class MatrixGraph
  38.     {
  39.         Graph graph = new Graph();
  40.  
  41.         public class Graph
  42.         {
  43.             /// <summary>
  44.             /// 顶点个数
  45.             /// </summary>
  46.             public char[] vertexs;
  47.  
  48.             /// <summary>
  49.             /// 边的条数
  50.             /// </summary>
  51.             public int[,] edges;
  52.  
  53.             /// <summary>
  54.             /// 顶点个数
  55.             /// </summary>
  56.             public int vertexsNum;
  57.  
  58.             /// <summary>
  59.             /// 边的个数
  60.             /// </summary>
  61.             public int edgesNum;
  62.         }
  63.  
  64.         #region 矩阵的构建
  65.         /// <summary>
  66.         /// 矩阵的构建
  67.         /// </summary>
  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.         /// <summary>
  106.         /// 边的信息
  107.         /// </summary>
  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.         /// <summary>
  123.         /// prim算法
  124.         /// </summary>
  125.         public Dictionary<char, Edge> Prim()
  126.         {
  127.             Dictionary<char, Edge> dic = new Dictionary<char, Edge>();
  128.  
  129.             //统计结果
  130.             Dictionary<char, Edge> outputDic = new Dictionary<char, Edge>();
  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. }