Chinaunix首页 | 论坛 | 博客
  • 博客访问: 465641
  • 博文数量: 85
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 32
  • 用 户 组: 普通用户
  • 注册时间: 2013-04-13 13:49
文章分类

全部博文(85)

文章存档

2018年(1)

2014年(40)

2013年(44)

分类: C/C++

2014-01-23 22:18:20

摘要:
  本文首先最小生成树三种算法简单描述,再介绍Prim算法描述、算法正确性证明并给出例子,最后用C语言实现该算法,并给出测试结果。

一、最小生成树算法
      现实中不少问题可以抽象成最小生成树模型,比如道路铺设,使得任何两个地方可达,并且使得总费用最省。最小生成树算法主要有:
(1) Kruskal(克鲁斯克尔)算法

      从G中的最小边开始,进行避圈式扩张。从符合扩展边(新加入的边不会构成回路)选择权值最小的边进行扩展。
(2) 管梅谷的破圈法
      不断破圈(从赋权图G的任意圈开始,去掉该圈中权值最大的一条边,称为破圈),直到G中没有圈为止,最后剩下的G的子图为G的最小生成树。
(3)  Prim算法
      对于连通赋权图G的任意一个顶点u,选择与点u关联的且权值最小的边作为最小生成树的第一条边e1。在接下来的边e2,e3,…,en-1 ,在与一条已经选取的边只有一个公共端点的的所有边中,选取权值最小的边。

       更多图论内容,详见经典博文《各种图论模型及其解答》。

二、Prim算法
(1) 算法描述
Prim算法利用贪心法思想,算法描述如下:
      在图G=(V, E) (V表示顶点 ,E表示边)中,从集合V中任取一个顶点(例如取顶点v0)放入集合 U中,这时 U={v0},集合T(E)为空。
      从v0出发寻找与U中顶点相邻(另一顶点在V中)权值最小的边的另一顶点v1,并使v1加入U。即U={v0,v1 },同时将该边加入集合T(E)中。
      重复(2),直到U = V为止。
  这时T(E)中有n-1条边,T = (U, T(E))就是一棵最小生成树。

(2) 算法正确性证明
      即证明用该算法得到的生成树是最小的。如下:
      设prim生成的树为G0,假设存在Gmin使得cost(Gmin)
(3) 例子

三、代码实现

注释比较清楚,源代码如下:

  1. /************************************
  2.  * 算法描述
  3.  *图用邻接矩阵存储adjMatrix[][]
  4.  *lowcost[i]表示当前生成树,到各顶点i的最小权值
  5.  * 当该点加入生成树,标记值为-1
  6.  *startVertex[i]与lowcost[i]对应的最小权值边的起点
  7.  *
  8.  *filename:prim_main.c
  9.  *by Jelline
  10.  * *********************************/


  11. #include <stdio.h>

  12. #define MAX_WEIGHT 0x7FFFFFFF

  13. //const int MAX_WEIGHT = 0x7FFFFFFF;
  14. //const int MAX_WEIGHT = 500;

  15. int prim(int n, int adjMatrix[][n], const char vertex[]);

  16. int main()
  17. {
  18.     const char vertex[] = {'a','b', 'c', 'd', 'e', 'f', 'g', 'h','i'};
  19.     const int n = sizeof(vertex)/sizeof(char); //the number of vertices

  20.     int adjMatrix[9][9] = {
  21.         {MAX_WEIGHT, 4, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 8, MAX_WEIGHT},
  22.         {4, MAX_WEIGHT, 8, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 11, MAX_WEIGHT},
  23.         {MAX_WEIGHT, 8, MAX_WEIGHT, 7, MAX_WEIGHT, 4, MAX_WEIGHT, MAX_WEIGHT, 2},
  24.         {MAX_WEIGHT, MAX_WEIGHT, 7, MAX_WEIGHT, 9, 14, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT},
  25.         {MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 9, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT},
  26.         {MAX_WEIGHT, MAX_WEIGHT, 4, 14, MAX_WEIGHT, MAX_WEIGHT, 2, MAX_WEIGHT, MAX_WEIGHT},
  27.         {MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 2, MAX_WEIGHT, 1, 6},
  28.         {8, 11, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 1, MAX_WEIGHT, 7},
  29.         {MAX_WEIGHT, MAX_WEIGHT, 2, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 6, 7, MAX_WEIGHT}
  30.     };

  31.     /*
  32.     int adjMatrix[9][9] = {
  33.         {0, 4, 0, 0, 0, 0, 0, 8, 0},
  34.         {4, 0, 8, 0, 0, 0, 0, 11, 0},
  35.         {0, 8, 0, 7, 0, 4, 0, 0, 2},
  36.         {0, 0, 7, 0, 9, 14, 0, 0, 0},
  37.         {0, 0, 0, 9, 10, 0, 0, 0, 0},
  38.         {0, 0, 4, 14, 10, 0, 2, 0, 0},
  39.         {0, 0, 0, 0, 0, 2, 0, 1, 6},
  40.         {8, 11, 0, 0, 0, 0, 1, 0, 7},
  41.         {0, 0, 2, 0, 0, 0, 6, 7, 0}
  42.     };
  43.     */

  44.     //prim(adjMatrix[][n]);
  45.     int sumWeight = prim(n, adjMatrix, vertex);
  46.     printf("the min sum of weight is %d\n", sumWeight);

  47.     return 0;
  48. }


  49. int prim(int n, int adjMatrix[][n], const char vertex[])
  50. {
  51.     int sumWeight = 0;
  52.     //lowcost[i]表示当前生成树,到各顶点i的最小权值 当该点加入生成树,标记值为-1
  53.     int lowcost[n];
  54.     int startVertex[n]; //startVertex[i]与lowcost[i]对应的最小权值边的起点
  55.     int minWeight; //最小权值
  56.     int minID; //对应minWeight的顶点

  57.     //默认选择第一个顶点加入边集合,第一次初始化lowcost
  58.     int i;
  59.     int j;

  60.     startVertex[0] = -1; //第一个顶点加入生成树
  61.     
  62.     for (i=1; i<n; i++) //以顶点0出发的所有边权值
  63.     {
  64.         startVertex[i] = 0;
  65.         lowcost[i] = adjMatrix[0][i];
  66.     }

  67.     for (i=1; i<n; i++) //生成树需要n-1个顶点
  68.     {
  69.         minWeight = MAX_WEIGHT; //初始化
  70.         minID = 0;

  71.         for (j=1; j<n; j++) //寻找权值最小的顶点
  72.         {
  73.             if(lowcost[j]<minWeight && lowcost[j]!=-1) //边权值最小且不在生成树中
  74.             {
  75.                 minWeight = lowcost[j];
  76.                 minID = j;
  77.             }
  78.         }

  79.         sumWeight += minWeight; //update the sumWeight
  80.         lowcost[minID] = -1; //标记顶点j已加入生成树

  81.         //print the edge
  82.         printf("%c----%c: %d\n", vertex[(startVertex[minID])], vertex[minID], minWeight);
  83.         

  84.         //更新当前结点minID到其他节点权值 而原lowcost[]已保存了之前顶点的最小权值
  85.         //即求未加入生成树的顶点到已加入顶点的最小权值
  86.         for (j=1; j<n; j++)
  87.         {
  88.             if (adjMatrix[minID][j] < lowcost[j])
  89.             {
  90.                 lowcost[j] = adjMatrix[minID][j];
  91.                 startVertex[j] = minID; //更新最小权值边的起点
  92.             }
  93.         }
  94.     }

  95.     return sumWeight;
  96. }

四、测试结果

用上述的例子进行测试,结果如下:

  1. a----b: 4
  2. b----c: 8
  3. c----i: 2
  4. c----f: 4
  5. f----g: 2
  6. g----h: 1
  7. c----d: 7
  8. d----e: 9
  9. the min sum of weight is 37



参考资料:
[1] 维基百科词条


阅读(1461) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~