问题描述

修路问题 - 图1

  • 有7个村庄(A, B, C, D, E, F, G) ，现在需要修路把7个村庄连通
  • 各个村庄的距离用边线表示(权) ，比如 A – B 距离 5公里
  • 问：如何修路保证各个村庄都能连通，并且总的修建公路总里程最短?
  • 正确的思路，就是尽可能的选择少的路线，并且每条路线最小，保证总里程数最少

思路步骤

  1. 从顶点开始处理：

    A-C[7]、A-G[2]、A-B[5]

  2. 开始，将A、G 顶点和它们相邻的还没有访问的顶点进行处理：

    A-C[7]、A-B[5]、G-B[3]、G-E[4]、G-F[6]

  3. 开始，将A、G、B 顶点和它们相邻的还没有访问的顶点进行处理：

    A-C[7]、G-E[4]、G-F[6]、B-D[9]

  4. 开始，将A、G、B、E顶点和它们相邻的还没有访问的顶点进行处理：

    A-C[7]、E-C[8]、E-F[5]、G-F[6]、B-D[9]

  5. 开始，将A、G、B、E、F顶点和它们相邻的还没有访问的顶点进行处理：

    A-C[7]、E-C[8]、B-D[9]、F-D[4]

  6. 开始，将A、G、B、E、F、D顶点和它们相邻的还没有访问的顶点进行处理：

    A-C[7]、E-C[8]

  7. 这么处理的话，7个顶点就有6条边。分别是A-G[2]，G-B[3]，G-E[4]，E-F[5]，F-D[4]，A-C[7]，加起来权值是25。这几条边连接起来就是最小生成树

    代码

    核心代码理解

    prim方法的三层循环是核心。
    prim方法传入的是0，说明以A为起始点，在下面的二维数组里面可以对照后面的数据。
    第一层循环代表有多少条边。二三层循环就是定位最小权值了。
    你会发现二三层循环如果没有if，就是遍历完了整个二维数组。
    visited[i] == 1表示二维数组的x轴，表示已经访问过的，比如一开始就给当前节点设置为访问过，当前节点是A，访问过了，就去检索y轴的数据那些顶点没访问。
    比如i=0，j=0时，不满足if，因为x轴是A访问过了，但是y轴也是A，A访问过了。
    当i=0，j=1是，x轴A访问过，y轴B没有访问过，第三个条件这个点的权值小于目前记录的最小权值，都满足条件，所以记录下来当前最小值。直到i=0，j=6时，x轴A，y轴G。记下了最小值的ij。
    j循环完了，i迭代，后面的循环第一个条件visited[i] == 1都不满足。直到i循环退出。这时候已经找到了一条边AG，G点也访问过了，标记。k迭代，表示找下一条边。
    这时候当x轴为A或者G时，才成立第一个条件，y轴又不能是A和G，因为已经找过了。这样的前提下，找到最小权值的坐标。GB这条边有了。
    如上
    再次循环x轴必须要是AGB三个才行，y轴是除了这三个的另外几个…… ```csharp using System; using System.Collections.Generic; using System.Globalization; using System.IO; using System.Runtime.Serialization.Formatters.Binary; using System.Text;

namespace ConsoleApp1 { class Program { static void Main(string[] args) { char[] data = new char[] { ‘A’, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’, ‘G’ }; int verxs = data.Length; //邻接矩阵的关系使用二维数组 //比如C和G之间不连通，就用8888来表示，权值太大就不考虑了 int x = 8888; int[,] weight = new int[,] { //A B C D E F G /A/{x, 5, 7, x, x, x, 2 }, /B/{5, x, x, 9, x, x, 3 }, /C/{7, x, x, x, 8, x, x }, /D/{x, 9, x, x, x, 4, x }, /E/{x, x, 8, x, x, 5, 4 }, /F/{x, x, x, 4, 5, x, 6 }, /G/{2, 3, x, x, 4, 6, x } }; //创建图 MGraph graph = new MGraph(verxs, data, weight); graph.Show(); prim(graph, 0); }

  1.     //编写prim算法,得到最小生成树
  2.     //graph对应的图,v从第几个顶点开始生成
  3.     public static void prim(MGraph graph, int v)
  4.     {
  5.         int[] visited = new int[graph.verxs];//标记节点(顶点),是否被访问过,默认都是0表示没访问过
  7.         //把当前这个节点标记为已经访问
  8.         visited[v] = 1;
  9.         //用h1和h2记录两个顶点的下标
  10.         int h1 = -1, h2 = -1;
  11.         int minWeight = 8888;//将minWeight初始化为一个大数,后面在便利过程中会被替换
  12.         for (int k = 1; k < graph.verxs; k++)//因为有graph.verxs个顶点,所以最小子图有graph.verxs-1条边
  13.         {
  14.             //确定每一次生成的子图,和哪个结点的距离最近
  15.             for (int i = 0; i < graph.verxs; i++)//i节点表示被访问过的节点
  16.             {
  17.                 for (int j = 0; j < graph.verxs; j++)//j节点表示还没有访问过的节点
  18.                 {
  19.                     if (visited[i] == 1 && visited[j] == 0 && graph.weight[i, j] < minWeight)
  20.                     {
  21.                         //寻找已经访问过的节点和未访问过的节点间的权值最小的边
  22.                         minWeight = graph.weight[i, j];
  23.                         h1 = i;
  24.                         h2 = j;
  25.                     }
  26.                 }
  27.             }
  28.             //退出for循环时,就找到了一条最小边
  29.             Console.WriteLine($"边{graph.data[h1]},{graph.data[h2]},权值{minWeight}");
  30.             //将当前这个节点标记为已经访问过的节点
  31.             visited[h2] = 1;
  32.             //minWeight从新设置为最大值
  33.             minWeight = 8888;
  34.         }
  35.     }
  37. }
  40. class MGraph
  41. {
  42.     public int verxs;//表示图的节点个数
  43.     public char[] data;//存放节点数据
  44.     public int[,] weight;//存放边，就是邻接矩阵
  46.     public MGraph(int verxs, char[] data, int[,] weight)
  47.     {
  48.         this.verxs = verxs;
  49.         this.data = data;
  50.         this.weight = weight;
  52.     }
  54.     public void Show()
  55.     {
  56.         for (int i = 0; i < weight.GetLength(0); i++)
  57.         {
  58.             for (int j = 0; j < weight.GetLength(1); j++)
  59.                 Console.Write(weight[i, j] + "   ");
  60.             Console.WriteLine();
  61.         }
  63.     }
  65. }

}

```