016-kruskal算法-贪心-《算法设计技巧与分析》M.H.A学习笔记
发布时间：2020-12-13 21:10:54 所属栏目：PHP教程 来源：网络整理
导读：最小生成树： 在1给定的连通 无向图 G = (V,E) 中， (u,v) 代表连接顶点 u 与顶点 v 的边，而 w(u,v) 代表此边的权重，若存在 T 为 G的 子集 且为无循环图，使得 w(T) 最小，则此 T 为G 的 最小生成树 。 基本思路： kruskal 算法 总共选择 n- 1 条边，所使
最小生成树：在1给定的连通无向图G = (V,E)中，(u,v) 代表连接顶点u与顶点v的边，而 w(u,v)代表此边的权重，若存在T为G的子集且为无循环图，使得w(T) 最小，则此T为G的最小生成树。
基本思路：kruskal算法总共选择n- 1条边，所使用的贪婪准则是：从剩下的边当选择1条不会产生环路的具有最小耗费的边加入已选择的边的集合中。注意到所选取的边若产生环路则不可能构成1棵生成树。kruskal算法分e 步，其中e 是网络中边的数目。按耗费递增的顺序来斟酌这e 条边，每次斟酌1条边。当斟酌某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。 概括以下： 1. 对G的边按权重非降序排列。 2. 1次取权重最小的边，如果把它放入T不会构成回路的话，则把它放入T中，否则将它抛弃。
判断是不是构成回路用并查集。
伪代码：
算法分析：主要耗费在边的排序，时间复杂度为O(mlogm)。
C++代码：struct edge {
int u,v,c;
bool operator < (const edge &b) const {
return c < b.c;
}
}e[mxe];
int n,m;
int fa[mnx];
int find(int x) {
if(fa[x] != x) fa[x] = find(fa[x]);
return fa[x];
}
// kruskal 复杂度O(|E|log|E|),|E|:边数
int kruskal() {
sort(e + 1,e + m + 1); // 边排序
for(int i = 1; i <= n; ++i) fa[i] = i; //并查集初始化
int ret = 0;
for(int i = 1; i <= m; ++i) {
int u = e[i].u,v = e[i].v,c = e[i].c;
u = find(u),v = find(v);
if(u != v) { //不在同1个集合里面,则把这1条边加入成为最小生成树的1部份
ret += c;
fa[u] = v;
}
}
return ret;
}
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
