您当前位置：首页 > php开源 > php教程 > 016-kruskal算法-贪心-《算法设计技巧与分析》M.H.A学习笔记

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

来源：程序员人生发布时间：2016-07-07 19:24:57 阅读次数：2799次

最小生成树：

在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; }

生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生

------分隔线----------------------------

上一篇 第一章 Web MVC简介 —— SpringMVC

下一篇 HTML5 表单属性

分享到:

------分隔线----------------------------

为码而活

积分：4237

15粉丝

7关注

栏目热点