Chinaunix首页 | 论坛 | 博客
  • 博客访问: 2877707
  • 博文数量: 471
  • 博客积分: 7081
  • 博客等级: 少将
  • 技术积分: 5369
  • 用 户 组: 普通用户
  • 注册时间: 2012-01-04 21:55
文章分类

全部博文(471)

文章存档

2014年(90)

2013年(69)

2012年(312)

分类: C/C++

2012-05-08 11:33:28

给定一个带权的无向连通图,如何选取一棵生成树,使树上所有边上权的总和为最小,这叫最小生成树.

求最小生成树的算法
(1) 克鲁斯卡尔算法
图的存贮结构采用
边集数组,且权值相等的边在数组中排列次序可以是任意的.该方法对于边相对比较多的不是很实用,浪费时间.

方法:将图中边按其权值由小到大的次序顺序选取,若选边后不形成回路,则保留作为一条边,若形成回路则除去.依次选够(n-1)条边,即得最小生成树,(n为顶点数)就是一个贪心算法;

Kruskal适合
一维数组来管理数据 ;
 
第一步:由边集数组选第一条边

第二步:选第二条边,即权值为2的边

第三步:选第三条边,即权值为3的边

第四步:选第四条边,即权值为4的边

第五步:选第五条边



点击(此处)折叠或打开

  1. /*
  2.  * Introduction to Algorithms
  3.  * Chapter 23 --- MST.Kruskal
  4.  * Tanky Woo @ www.WuTianQi.com
  5.  * 2012.1.7
  6.  */
  7.  
  8. #include <iostream>
  9. #include <algorithm>
  10. using namespace std;
  11.  
  12. const int maxint = 999999;
  13.  
  14. typedef struct Road{
  15.     int c1, c2; // a到b
  16.     int value; // 权值
  17. }Road;
  18.  
  19. int no;
  20. int line;//记录实际关系数
  21. Road road[100];//设一个比较大的值,实际看输入最小生成树中:边数e=n-1
  22. int node[101];//最小生成树:n顶点数
  23.  
  24. bool myCmp(const Road &a, const Road &b)
  25. {
  26.     if(a.value < b.value)
  27.         return 1;
  28.     return 0;
  29. }
  30.  
  31. //node[2]=1 node[8]=1 ,node[3]=1,共同的祖先,如果(3,8)加进去,则构成回路,不要
  32. //有点像并查集
  33. int Find_Set(int n)
  34. {
  35.     if(node[n] == -1)
  36.         return n;
  37.     return node[n] = Find_Set(node[n]);
  38. }
  39.  
  40. bool Merge(int s1, int s2)
  41. {
  42.     int r1 = Find_Set(s1);
  43.     int r2 = Find_Set(s2);
  44.     if(r1 == r2)//如果相等证明构成回路,则直接返回一个0,不要把顶点加进来(下一步是加进去的)
  45.         return 0;
  46.     if(r1 < r2)
  47.         node[r2] = r1;
  48.     else
  49.         node[r1] = r2;
  50.     return 1;
  51. }
  52.  
  53. int main()
  54. {
  55.     freopen("input.txt", "r", stdin);
  56.     //初始化全为-1
  57.     memset(node, -1, sizeof(node));
  58.     scanf("%d",&no);
  59.     scanf("%d",&line);
  60.     int i;
  61.     for(i=0; i<line; ++i)
  62.     {
  63.         cin >> road[i].c1 >> road[i].c2 >> road[i].value;
  64.     }
  65.     sort(road, road+line, myCmp);
  66.     int sum = 0, count = 0; // sum是MST的值,count是记录已使用的点数
  67.     for(i=0; i<line; ++i)
  68.     {
  69.         if(Merge(road[i].c1, road[i].c2))//如果返回的为0,则证明构成回路,不要加进
  70.         {
  71.             count ++;
  72.             sum += road[i].value;
  73.         }
  74.         if(count == no-1)//e=n-1已经连通,可以退出
  75.             break;
  76.     }
  77.     cout << sum << endl;
  78.     return 0;
  79. }
  80.  
  81.  
  82. /*
  83. input.txt:
  84. 9
  85. 14
  86. 1 2 4
  87. 1 8 8
  88. 2 3 8
  89. 2 8 11
  90. 3 4 7
  91. 3 6 4
  92. 3 9 2
  93. 4 5 9
  94. 4 6 14
  95. 5 6 10
  96. 6 7 2
  97. 7 8 1
  98. 7 9 6
  99. 8 9 7
  100. */

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