1.普里姆算法

  1. // Prim算法生成最小生成树
  2. void MiniSpanTree_Prim(MGraph G)
  3. {
  4.     int min, i, j, k;
  5.     int adjvex[MAXVEX];        // 保存相关顶点下标
  6.     int lowcost[MAXVEX];    // 保存相关顶点间边的权值
  8.     lowcost[0] = 0;            // V0作为最小生成树的根开始遍历，权值为0
  9.     adjvex[0] = 0;            // V0第一个加入
  11.     // 初始化操作
  12.     for( i=1; i < G.numVertexes; i++ )
  13.     {
  14.         lowcost[i] = G.arc[0][i];    // 将邻接矩阵第0行所有权值先加入数组
  15.         adjvex[i] = 0;                // 初始化全部先为V0的下标
  16.     }
  18.     // 真正构造最小生成树的过程
  19.     for( i=1; i < G.numVertexes; i++ )
  20.     {
  21.         min = INFINITY;        // 初始化最小权值为65535等不可能数值
  22.         j = 1;
  23.         k = 0;
  25.         // 遍历全部顶点
  26.         while( j < G.numVertexes )
  27.         {
  28.             // 找出lowcost数组已存储的最小权值
  29.             if( lowcost[j]!=0 && lowcost[j] < min )
  30.             {
  31.                 min = lowcost[j];
  32.                 k = j;        // 将发现的最小权值的下标存入k，以待使用。
  33.             }
  34.             j++;
  35.         }
  37.         // 打印当前顶点边中权值最小的边
  38.         printf("(%d,%d)", adjvex[k], k);
  39.         lowcost[k] = 0;        // 将当前顶点的权值设置为0，表示此顶点已经完成任务，进行下一个顶点的遍历
  41.         // 邻接矩阵k行逐个遍历全部顶点
  42.         for( j=1; j < G.numVertexes; j++ )
  43.         {
  44.             if( lowcost[j]!=0 && G.arc[k][j] < lowcost[j] )
  45.             {
  46.                 lowcost[j] = G.arc[k][j];
  47.                 adjvex[j] = k;    
  48.             }
  49.         }
  50.     }
  51. }

2.克鲁斯卡尔算法

  2. int Find(int *parent, int f)
  3. {
  4.     while( parent[f] > 0 )
  5.     {
  6.         f = parent[f];
  7.     }
  9.     return f;
  10. }
  12. // Kruskal算法生成最小生成树
  13. void MiniSpanTree_Kruskal(MGraph G)
  14. {
  15.     int i, n, m;
  16.     Edge edges[MAGEDGE];    // 定义边集数组
  17.     int parent[MAXVEX];        // 定义parent数组用来判断边与边是否形成环路
  19.     for( i=0; i < G.numVertexes; i++ )
  20.     {
  21.         parent[i] = 0;
  22.     }
  24.     for( i=0; i < G.numEdges; i++ )
  25.     {
  26.         n = Find(parent, edges[i].begin);    // 4 2 0 1 5 3 8 6 6 6 7
  27.         m = Find(parent, edges[i].end);        // 7 8 1 5 8 7 6 6 6 7 7
  29.         if( n != m )        // 如果n==m，则形成环路，不满足！
  30.         {
  31.             parent[n] = m;    // 将此边的结尾顶点放入下标为起点的parent数组中，表示此顶点已经在生成树集合中
  32.             printf("(%d, %d) %d ", edges[i].begin, edges[i].end, edges[i].weight);
  33.         }
  34.     }
  35. }

无论是普里姆算法（Prim）还是克鲁斯卡尔算法（Kruskal），他们考虑问题的出发点都是：为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能的小。
普里姆算法是以某顶点为起点，逐步找各个顶点上最小权值的边来构建最小生成树的。
克鲁斯卡尔算法是我们从边出发，因为权值是在边上嘛，直接去找最小权值的边来构建生成树是自然的想法，这也是克鲁斯卡尔算法的精髓。