最小生成树

最小生成树在实际生活中的应用非常广泛，可以在很多地方看到最小生成树应用的实例。例如：在一个偏僻的村庄，村户都散落在村庄四处，现在需要进行供电建设，需要使用一条电缆将每家每户连接起来，由于村户距离都间隔比较远，那么这时候需要考虑到成本问题，就需要用最短的距离去连接，而最小生成树的成本就是最少的

• 什么是最小生成树：
  对于一个图来说，如果一个子图包含了图中所有的节点，那么这个子图称为图的一个生成树，在所有子图中，边的权值相加得到的总和最小的子图，称为最小生成树。

• 最小生成树的求解算法

  • Prim算法
  • Kruskal算法

  两种算法都采用了贪心的思想，关于贪心的思想，这里先给出解释：贪心的思想核心为在求解问题的时候，只是考虑到当前情况下的最优解，而不是全局的，所以说其实是局部上的最优解，因此贪心的思想不是总是最好的，使用贪心算法必须考虑到是否局部的求解是否会影响到后面，如果会影响，那么贪心算法的效果往往不尽人意。

• Prim算法

  • Prim算法的求解思想：
    先选择一个点，然后选出最短路径，找到这个最短路径连接的点，然后再比较这两个点到其他点的最短路径，依次按照这种贪心思想进行下去，直到每个顶点都被找到。
  • Prim算法的具体代码：

int c[MAXINT][MAXINT]={{32767,6,1,5,32767,32767},{6,32767,5,32767,3,32767},{1,5,32767,5,6,4},{5,32767,5,32767,32767,2},{32767,3,6,32767,32767,6},{32767,32767,4,2,6,32767}};
void Prim(int n)
{
      int lowcost[MAXINT];// 存储最小生成树中的节点到达其他节点的最短距离
      int closest[MAXINT];// 其他节点到达最小生成树中最近的节点（实际上就是前驱节点）
      bool visited[MAXINT];//bool型变量的S数组表示i是否已经包括在S中
      int i,k;
      visited[0] = true;//从第一个结点开始
      for(i = 1; i <= n; i++)//简单初始化
      {
          lowcost[i] = c[0][i];
          closest[i] = 0; //现在所有的点对应的生成树的最近的点是0
          visited[i] = false;
      }
      for(i = 0; i < n; i++)
      {
         int min = 32767;
         int j = 1;
         for(k = 1; k <= n; k++)//寻找lowcost中的最小值
          {
             if((lowcost[k] < min)&&(!visited[k]))
              {
                 min = lowcost[k];
                 j = k;
              }
          }
          visited[j] = true;
          for(k = 1; k <= n; k++)//因为新加入了j点,所以要查找新加入的j点到未在生成树中的点K中的权值是不是可以因此更小
          {
            if((c[j][k] < lowcost[k])&&(!visited[k])) {
                lowcost[k] =c [j][k];
                closest[k] = j;
              }
          }
      }
  }

• Prim算法的细节分析
  可以发现，Prim算法中使用到了三个数组：

  • lowcost [ ]：用来存储最小生成树中的节点到达其他节点的最短距离
  • closest [ ]：用来存储其他节点到最小生成树中最近的点（实际上是为了打印最小生成树而建立的前驱节点集合）
  • visited [ ]：用来存储每个节点的状态（是否已经在最小生成树中了）

  使用到了三个循环：

  • 第一个循环：是循环N次，每次加入一个节点到生成树中
  • 第二个循环：找到当前lowcost中最小值，并且将改点添加到生成树中来
  • 第三个循环：由于新添加了节点，所以需要更新一下lowcost中每个节点的值，同时将符合条件的节点的前驱节点设置为这个新添加的节点

• Kruskal算法

  • Kruskal算法的求解思想：
    求解过程其实是以边为核心的，首先会将所有的边进行排序，按照权重的升序进行排列，然后依次取出，取出的操作为，如果这条边的两个顶点在最小生成树的不同的连通分量中，那么就讲这条边加入到最小生成树中，如果这条边的两个顶点在相同的连通分量中，那么就忽视掉这条边，对下一条边进行操作，直到所有顶点都被加入到了最小生成树中。