016-kruskal算法-贪心-《算法设计技巧与分析》M.H.A学习笔记


最小生成树:

在1给定的连通无向图G = (V, E)中,(u, v)
代表连接顶点u与顶点v的边,而
w(u, v)代表此边的权重,若存在TG的子集且为无循环图,使得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;
}

 

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » 016-kruskal算法-贪心-《算法设计技巧与分析》M.H.A学习笔记

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡