首页 > 编程语言 > 详细

无向图最小生成树之kruskal算法

时间:2021-07-20 23:09:53      阅读:9      评论:0      收藏:0      [点我收藏+]

kruskal算法:通过每次查找最小边直到连到n-1条边为止。

题目来源

N个点M条边的无向连通图,每条边有一个权值,求该图的最小生成树。

输入

第1行:2个数N, M中间用空格分隔,N为点的数量,M为边的数量。(2 <= N <= 1000, 1 <= M <= 50000)

第2 - M + 1行:每行3个数S E W,分别表示M条边的2个顶点及权值。(1 <= S, E <= N,1 <= W <= 10000)


 

输出

输出最小生成树的所有边的权值之和。

 

 

输入样例

9 14
1 2 4
2 3 8
3 4 7
4 5 9
5 6 10
6 7 2
7 8 1
8 9 7
2 8 11
3 9 2
7 9 6
3 6 4
4 6 14
1 8 8

输出样例

37

 

源代码:

 1 #include <iostream>
 2 #include <queue>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 int fa[1010],ran[1010];
 7 int t = 0;
 8 
 9 struct Edge {    
10     int s, e, w;  //s点,e点,w两点距离
11 }edge[50050];
12 
13 int cmp(Edge x, Edge y) {
14     return x.w < y.w;    //按两点的距离从小到大排序
15 }
16 
17 void init(int n) {
18     for (int i = 1; i <= n; i++) {
19         fa[i] = i;      //初始化,每个点只连自己
20         ran[i] = 1;      //ran[]记录每个点的深度
21     }
22 }
23 
24 int fin(int x) {
25     return fa[x] == x ? x : (fa[x] = fin(fa[x]));    //并查集(递归找根节点)
26 }
27 
28 void uni(int i, int j) {            //并查集(合并两点,生成一颗树)
29     int x = fin(i), y = fin(j);
30     if (x == y) return;
31     if (ran[x] < ran[y])          //按深度合并,把小树和到大树上
32         fa[x] = y;
33     else fa[y] = x;
34 
35     if (ran[x] == ran[y] && x != y)
36         ran[y]++;
37 }
38 
39 int kruskal(int a, int b, int c) {      //kruskal算法(a--点,b--点,c--两点距离)
40     int sum = 0;      
41     if (fin(a) != fin(b)) {      //判断两点相连是否成环(根节点是否相同),没相连就合并两个点
42         uni(a, b);
43         sum = c;
44         t++;            //用做统计已相连的边数
45     }
46     return sum;          //返回两点之间距离的值
47 }
48 
49 int main() {
50     int n, m;
51     cin >> n >> m;      //输入n个点,m条边
52     init(n);          //将n个点初始化
53 
54     for (int i = 0; i < m; i++){
55         cin >> edge[i].s >> edge[i].e >> edge[i].w;    //输入m条边的两端点,和两点之间距离
56     }
57 
58     sort(edge, edge + m, cmp);      //按两点之间距离从小到大排序
59     int s = 0, ss = 0;          
60 
61     for (int i = 0; i < m; i++) {
62         s = kruskal(edge[i].s, edge[i].e, edge[i].w);
63         ss += s;          //将生成树上所有的值都加起来,就是最小生成树的值了
64         if (t == n-1) break;    //n个点只需要n-1条边就可以全部连起来了
65     }
66     cout << ss << endl;    //输出最小生成树的值
67 }

 

无向图最小生成树之kruskal算法

原文:https://www.cnblogs.com/Gu-yi/p/15036705.html

(0)
(0)
   
举报
评论 一句话评论(0
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!