给定一个带权的无向连通图,如何选取一棵生成树,使树上所有边上权的总和为最小,这叫最小生成树.
求最小生成树的算法
(1) 克鲁斯卡尔算法
图的存贮结构采用边集数组,且权值相等的边在数组中排列次序可以是任意的.该方法对于边相对比较多的不是很实用,浪费时间.
方法:将图中边按其权值由小到大的次序顺序选取,若选边后不形成回路,则保留作为一条边,若形成回路则除去.依次选够(n-1)条边,即得最小生成树,(n为顶点数)就是一个贪心算法;
Kruskal适合一维数组来管理数据 ;
第一步:由边集数组选第一条边
第二步:选第二条边,即权值为2的边
第三步:选第三条边,即权值为3的边
第四步:选第四条边,即权值为4的边
第五步:选第五条边
- /*
- * Introduction to Algorithms
- * Chapter 23 --- MST.Kruskal
- * Tanky Woo @ www.WuTianQi.com
- * 2012.1.7
- */
-
- #include <iostream>
- #include <algorithm>
- using namespace std;
-
- const int maxint = 999999;
-
- typedef struct Road{
- int c1, c2; // a到b
- int value; // 权值
- }Road;
-
- int no;
- int line;//记录实际关系数
- Road road[100];//设一个比较大的值,实际看输入最小生成树中:边数e=n-1
- int node[101];//最小生成树:n顶点数
-
- bool myCmp(const Road &a, const Road &b)
- {
- if(a.value < b.value)
- return 1;
- return 0;
- }
-
- //node[2]=1 node[8]=1 ,node[3]=1,共同的祖先,如果(3,8)加进去,则构成回路,不要
- //有点像并查集
- int Find_Set(int n)
- {
- if(node[n] == -1)
- return n;
- return node[n] = Find_Set(node[n]);
- }
-
- bool Merge(int s1, int s2)
- {
- int r1 = Find_Set(s1);
- int r2 = Find_Set(s2);
- if(r1 == r2)//如果相等证明构成回路,则直接返回一个0,不要把顶点加进来(下一步是加进去的)
- return 0;
- if(r1 < r2)
- node[r2] = r1;
- else
- node[r1] = r2;
- return 1;
- }
-
- int main()
- {
- freopen("input.txt", "r", stdin);
- //初始化全为-1
- memset(node, -1, sizeof(node));
- scanf("%d",&no);
- scanf("%d",&line);
- int i;
- for(i=0; i<line; ++i)
- {
- cin >> road[i].c1 >> road[i].c2 >> road[i].value;
- }
- sort(road, road+line, myCmp);
- int sum = 0, count = 0; // sum是MST的值,count是记录已使用的点数
- for(i=0; i<line; ++i)
- {
- if(Merge(road[i].c1, road[i].c2))//如果返回的为0,则证明构成回路,不要加进
- {
- count ++;
- sum += road[i].value;
- }
- if(count == no-1)//e=n-1已经连通,可以退出
- break;
- }
- cout << sum << endl;
- return 0;
- }
-
-
- /*
- input.txt:
- 9
- 14
- 1 2 4
- 1 8 8
- 2 3 8
- 2 8 11
- 3 4 7
- 3 6 4
- 3 9 2
- 4 5 9
- 4 6 14
- 5 6 10
- 6 7 2
- 7 8 1
- 7 9 6
- 8 9 7
- */
阅读(5329) | 评论(0) | 转发(1) |