克鲁斯卡尔算法(Kruskal算法)求最小生成树

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了克鲁斯卡尔算法(Kruskal算法)求最小生成树，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1743字，纯文字阅读大概需要3分钟。

内容图文

题目传送：https://loj.ac/p/10065

 

1、排序函数sort，任何一种排序算法都行，下面的示例代码中，我采用的是冒泡排序算法

2、寻源函数getRoot，寻找某一个点在并查集中的根，注意，是根，不是双亲！，所以，判断的条件为如果某一个下标的值就是其本身，设a为并查集数组，v为数组值，如果a[v] = v，它就是根，否则就让v = a[v]，向上寻找，直到其相等。

 

1图的存储结构(a，b为边的两个顶点，w为边的权值),初始化

2.排序sort函数（按照权值从小到大）

3.getRoot寻源函数（v为并查集，x为待查顶点）

4.for循环遍历

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define x first
 4 #define y second
 5 const int mx= 250100;
 6 int n,k;
 7 typedef pair<int,int> PII;
 8 struct node{
 9     int x,y;
10     double z;
11 }; 
12 bool operator <(node &a,node &b)
13 {
14     return a.z<b.z;
15 }
16 
17 int f[mx];
18 PII q[mx];
19 node edge[mx];
20 
21 int get(int x)
22 {
23     return x==f[x]?x:get(f[x]);
24 } 
25 
26 double getdist(PII a,PII b)
27 {
28     int dx=a.x-b.x;
29     int dy=a.y-b.y;
30     return sqrt(dx*dx+dy*dy);
31 }
32 
33 int main()
34 {
35     cin>>n>>k;
36     for(int i=1;i<=n;i++)
37     {
38         cin>>q[i].x>>q[i].y;
39     }
40     int m=0;
41     for(int i=1;i<=n;i++)
42     {
43         for(int j=1;j<=i;j++)
44         {
45             edge[++m].x=i;
46             edge[m].y=j;
47             edge[m].z=getdist(q[i],q[j]);
48         }
49     }
50     sort(edge+1,edge+1+m);
51     for(int i=1;i<=m;i++) f[i]=i;
52     int cnt=n;
53     double ans=0;
54     for(int i=1;i<=m;i++)
55     {
56         if(cnt<=k) break;
57         int a=get(edge[i].x),b=get(edge[i].y);
58         double w=edge[i].z;
59         if(a!=b)
60         {
61             f[a]=b;
62             cnt--;
63             ans=w;
64         }
65      } 
66      printf("%.2lf\n",ans);
67 }

 

内容总结

以上是互联网集市为您收集整理的克鲁斯卡尔算法(Kruskal算法)求最小生成树全部内容，希望文章能够帮你解决克鲁斯卡尔算法(Kruskal算法)求最小生成树所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---