Top

Kruskal模板 - 最小生成树


此算法可以称为“加边法”,初始最小生成树边数为0,每迭代一次就选择一条满足条件的最小代价边,加入到最小生成树的边集合里。

  1. 把图中的所有边按代价从小到大排序;
  2. 把图中的n个顶点看成独立的n棵树组成的森林;
  3. 按权值从小到大选择边,所选的边连接的两个顶点ui,viui,vi,应属于两颗不同的树,则成为最小生成树的一条边,并将这两颗树合并作为一颗树。
  4. 重复(3),直到所有顶点都在一颗树内或者有n-1条边为止。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define MAXN 11 //顶点个数的最大值
#define MAXM 20 //边的个数的最大值
using namespace std;

struct edge //边
{
int u, v, w; //边的顶点、权值
}edges[MAXM]; //边的数组

int parent[MAXN]; //parent[i]为顶点 i 所在集合对应的树中的根结点
int n, m; //顶点个数、边的个数
int i, j; //循环变量
void UFset( ) //初始化
{
for( i=1; i<=n; i++ )
parent[i] = -1;
}
int Find( int x ) //查找并返回节点 x 所属集合的根结点
{
int s; //查找位置
for( s=x; parent[s]>=0; s=parent[s] );
while( s!=x ) //优化方案―压缩路径,使后续的查找操作加速。
{
int tmp = parent[x];
parent[x] = s;
x = tmp;
}
return s;
}

//将两个不同集合的元素进行合并,使两个集合中任两个元素都连通
void Union( int R1, int R2 )
{
int r1 = Find(R1), r2 = Find(R2); //r1 为 R1 的根结点,r2 为 R2 的根结点
int tmp = parent[r1] + parent[r2]; //两个集合结点个数之和(负数)
//如果 R2 所在树结点个数 > R1 所在树结点个数(注意 parent[r1]是负数)
if( parent[r1] > parent[r2] ) //优化方案――加权法则
{
parent[r1] = r2;
parent[r2] = tmp;
}
else
{
parent[r2] = r1;
parent[r1] = tmp;
}
}
bool cmp( edge a, edge b ) //实现从小到大排序的比较函数
{
return a.w <= b.w;
}
void Kruskal( )
{
int sumweight = 0; //生成树的权值
int num = 0; //已选用的边的数目
int u, v; //选用边的两个顶点
UFset( ); //初始化 parent[]数组
for( i=0; i<m; i++ )
{
u = edges[i].u; v = edges[i].v;
if( Find(u) != Find(v) )
{
printf( "%d %d %d\n", u, v, edges[i].w );
sumweight += edges[i].w; num++;
Union( u, v );
}
if( num>=n-1 ) break;
}
printf( "weight of MST is %d\n", sumweight );
}
int main( )
{
int u, v, w; //边的起点和终点及权值
scanf( "%d%d", &n, &m ); //读入顶点个数 n
for( int i=0; i<m; i++ )
{
scanf( "%d%d%d", &u, &v, &w ); //读入边的起点和终点
edges[i].u = u; edges[i].v = v; edges[i].w = w;
}
sort(edges,edges+m,cmp);
Kruskal();
return 0;
}
文章版权为Anoyer博客所有,转载请以链接形式标明本文地址