网页首站,软件生成器手机版,企业建立站点方案有几种,商业网站建设规划书目录
一、最小生成树
二、Kruskal算法求最小生成树
三、代码 一、最小生成树
什么是最小生成树#xff1f;
对于一个n个节点的带权图#xff0c;从中选出n-1条边#xff08;保持每个节点的联通#xff09;构成一棵树#xff08;不能带环#xff09;#xff0c;使得…目录
一、最小生成树
二、Kruskal算法求最小生成树
三、代码 一、最小生成树
什么是最小生成树
对于一个n个节点的带权图从中选出n-1条边保持每个节点的联通构成一棵树不能带环使得所有边的权值和最小即为最小生成树
要点
选n-1条边要构成一颗树则树中不能带环节点间要互相连通即从一个节点能够到达任意一个节点边的权重和最小 二、Kruskal算法求最小生成树
Kruskal算法适用于稀疏图因为其过程基于边的选择如果图中的边过多可能导致效率变低
其思路如下
将图中的所有边去掉只留下节点按照边权的顺序从权重小的边开始将边回填到图中如果某个边回填到图中会导致带环则丢弃当回填了n-1条边得到最小生成树
例如
这是我们的原图 去掉所有的边 按照权重从小到大回填边 此时发现有两条权重为4的边选择哪条都可以这也说明我们的最小生成树并不是唯一的但最小权重和一定是唯一的 此时有两条权重为5的边但如果我们把V1和V4之间的边回填的话就带环了这是不符合要求的因此我们选择V2和V3之间的边 此时已经选择了n-1条边我们的最小生成树就为 三、代码
Kruskal算法的思想很容易理解但代码实现还是有些难度的
例如我们该如何判断图中是否带环呢其实很简单如果在回填某条边时边两端的节点位于同一个集合中就说明带环。我们可以使用并查集来判断
关于并查集可以阅读
【算法】并查集-CSDN博客https://blog.csdn.net/Eristic0618/article/details/138584962接下来写一道例题练练手
P3366 【模板】最小生成树 - 洛谷 | 计算机科学教育新生态 #include bits/stdc.h
#define int long long
#define endl \n
#define debug(x) cout #x x \n
#define INF 0x3f3f3f3f
using namespace std;#define N 5050
#define M 200020int n, m;
int f[N]; //并查集 struct edge
{int a, b, w;
}e[M];int cmp(struct edge a, struct edge b)
{return a.w b.w;
}int check(int num) //查询某个节点所在集合的根
{if(f[num] ! num) return f[num] check(f[num]); //压缩路径将路径上每个节点的父亲都修改为根节点 return num;
}void merge(int a, int b) //合并两个节点所在集合
{if(a b) //a,b相同 return;f[a] b; //a的父节点置为b
} bool same(int a, int b) //判断两个节点是否在同一集合
{if(f[a] f[b]) return true; //a,b父节点相同说明在同一集合 else return false;
}int Kruskal()
{for(int i 1; i n; i) //初始化并查集 {f[i] i;}sort(e, em, cmp); //按照边权升序排序 int cnt 0; //统计当前选择了多少条边 int ans 0; //最小生成树边权和 for(int i 0;i m; i) //遍历所有边 {int a e[i].a, b e[i].b, w e[i].w;a check(a), b check(b);if(same(a, b)) //a与b处于同一连通分量continue;//a与b不处于同一连通分量ans w; //选择该条边merge(a, b); //将ab所在连通分量合并 cnt;if(cnt n-1) //已选择n-1条边 break;} if(cnt n-1) //边数不足return -1;return ans;
}void solve()
{cin n m;for(int i 0;i m; i){int x, y, z;cin x y z;e[i] {x, y, z}; //存边 }int ans Kruskal(); //Kruskal算法if(ans -1) //不连通 cout orz endl;elsecout ans endl;
}signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t 1;//cin t;while(t--)solve();return 0;
}
完.
