kruscal 算法 最小生成树模板(hdu 1233 )

kruskal 和 prim 算法都是求最小生成树经常用到的算法,其中,prim 适用于稠密图(边较多),而 kruskal 更适用于稀疏图(边较少)。其时间复杂度为 O(elog2(e)). 其中,e 为图的边 AD 和 CE 是最短边,长度为 5,AD 是 第一个选择的边,被突出显示。 CE 现在是不构成循环的第二条最短的边,长度为 5,突出显示为第二个边。 下一条边,长度为 6 的 DF,突出显示为第三条边。 接下来的最短边是 AB 和 BE,都是长度为 7. 随机选一条,这里我们选 AB,并且突出显示。边缘 BD 以红色突出显示,因为在 B 和 D 之间已经存在一条路径(绿色),所以如果选择它,它将形成一个循环(ABD)。 继续突出显示下一条最小的边,BE 长度为 7. 许多个边缘以红色显示:BC,因为它会形成回路 BCE。DE,因为它会形成回路 DEBA 和 FE 因为它会形成 FEBAD。 最后,该过程以长度为 9 的边 EG 结束,并找到最小生成树。 kruskal 和 prim 都是基于贪心的思想,其中,kruskal 是每次将属于不同集合的最小的一条边合并。这样,一直合并下去,最终会得到一棵最小生成树(总点数一定,连接的点不断增多,所以未连接的点就会逐渐减少直到为 0),需要注意的是,kruskal 是基于并查集优化的,所以了解 kruskal 算法之前,应该先看一下并查集。

  1. 使用结构体储存边的信息:

    struct edge{

    int a,b;        //a为起点,b为终点
    int v;          //v为该边的权值
    

    }s[maxn];///将结构体按权值排序后,依次进行合并操作

  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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
int pre[maxn];    ///各集合

int Find(int a){        ///寻找祖宗节点的同时进行路径压缩
int root = a;
int tmp;
while(root != pre[root])root = pre[root];
while(a != root){
tmp = a;
a = pre[a];
pre[tmp] = root;
}
return root;
}

void combine(int a,int b){    ///合并a,b两个集合,这里我们规定将较大的数并入到较小的数中
int x = Find(a);
int y = Find(b);
if(x > y)
swap(x,y);
pre[y] = x;
}
3;kruskal 主代码:

int kruscal(int n,int m){
int ans = 0;
For(i,m){
if(Find(s[i].a)!=Find(s[i].b)){    ///如果a点所在的集合和b点所在的集合不相交
combine(s[i].a,s[i].b);        ///合并两个集合
ans += s[i].v;                
n--;
}
if(n == 1)    ///当已经连了n-1条边时,就已经构成了最小生成树因为每n个点要连在一起只需要n-1条线即可
break;
}
return ans;
}
```

* * *

例题:hdu1233 某省调查乡村交通状况,得到的统计表中列出了任意两村庄间的距离。省政府 “畅通工程” 的目标是使全省任何两个村庄间都可以实现公路交通(但不一定有直接的公路相连,只要能间接通过公路可达即可),并要求铺设的公路总长度为最小。请计算最小的公路总长度。 

**Input**

测试输入包含若干测试用例。每个测试用例的第 1 行给出村庄数目 N (< 100);随后的 N (N-1)/2 行对应村庄间的距离,每行给出一对正整数,分别是两个村庄的编号,以及此两村庄间的距离。为简单起见,村庄从 1 到 N 编号。  当 N 为 0 时,输入结束,该用例不被处理。 

**Output**

对每个测试用例,在 1 行里输出最小的公路总长度。 

**Sample Input**

3 1 2 1 1 3 2 2 3 4 4 1 2 1 1 3 4 1 4 1 2 3 3 2 4 2 3 4 5 0

**Sample Output**

3 5

Huge input, scanf is recommended.    

裸 kruskal 即可 参考代码:
```cpp
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <cstring>
#define For(i,n) for(int i=0;i<n;i++)
#define mem(a) memset(a,0,sizeof(a))
using namespace std;

const int INF = 0x3f3f3f3f;
const int maxn = 1e4+5;
typedef long long ll;

struct edge{
int a,b;
int v;
}s[maxn];

int pre[maxn];

bool cmp(edge a,edge b){return a.v < b.v;}
int Find(int a){
int root = a;
int tmp;
while(root != pre[root])root = pre[root];
while(a != root){
tmp = a;
a = pre[a];
pre[tmp] = root;
}
return root;
}

void combine(int a,int b){
int x = Find(a);
int y = Find(b);
if(x > y)
swap(x,y);
pre[y] = x;
}

int kruscal(int n,int m){
int ans = 0;
For(i,m){
if(Find(s[i].a)!=Find(s[i].b)){
combine(s[i].a,s[i].b);
ans += s[i].v;
n--;
}
if(n == 1)
break;
}
cout << ans <<endl;


}
int main() {
int n;
int a,b,c;
int cnt;
while(cin >> n && n){
mem(s);
For(i,n+1)
pre[i] = i;
cnt = 0;
For(j,n*(n-1)/2){
cin >> a >> b>>c ;
s[cnt].a = a;
s[cnt].b = b;
s[cnt++].v = c;
}
sort(s,s+cnt,cmp);            ///将边的权值按从小到大排序
kruscal(n,n*(n-1)/2);         ///一共n个点,n*(n-1)/2条边
}


return 0;
}
觉得文章不错的话可以请我喝一杯茶哟~
  • 本文作者: bestsort
  • 本文链接: https://bestsort.cn/2019/04/22/114/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-SA 许可协议。转载请注明出处!并保留本声明。感谢您的阅读和支持!
-------------本文结束感谢您的阅读-------------