常熟做网站优化,免费搭建微商城,中国十大门窗品牌,久久建筑网会员怎么样一、算法原理
Kruskal 算法用于求最小生成树#xff0c;它的主要思路是基于并查集#xff0c;算法的主要原理如下#xff1a;
假设图中有 n 个点#xff0c;则#xff1a; step 1#xff1a;Kruskal 算法假定初始时每个点都只属于自己所在的并查集#xff08;即初始时…一、算法原理
Kruskal 算法用于求最小生成树它的主要思路是基于并查集算法的主要原理如下
假设图中有 n 个点则 step 1Kruskal 算法假定初始时每个点都只属于自己所在的并查集即初始时每个点都只属于一个独立的集合各集合之间没有任何交集。代码实现如下 // p[a] S表示点a属于集合S
for (int i 1; i n; i) p[i] i;step 2将所有的边假设图中共有 m 条按权重从小到大进行排序因为 Kruskal 算法是按照边的权重从小到大进行遍历的排序的目的是为了保证在向当前的生成树中加入边时加入的始终都是权重最小的边其实也有点类似于贪心这样当所有的边遍历完后最终生成树中的所有边之和必然是全局最小的。代码实现如下 // 重载Edge对象的使之能够进行小于运算
struct Edge
{int a, b, w;bool operator(const Edge e) const{return w e.w;}
}edges[M];sort(edges, edges m);step 3按边的权重从小到大遍历所有边取出边的两个顶点然后进行判断 如果边的两个顶点不在同一个并查集中则将这两个顶点加入同一个并查集相当于将这两个顶点和它们之间的连边加入最小生成树然后将边的长度累加至最终结果并记录当前生成树中又加入了一条边这个记录是为了判断图中有没有可能不存在最小生成树如果最终得到的生成树中的边数不到 n − 1 n-1 n−1 条 n n n 个点总共需有 n − 1 n-1 n−1 条边则说明图中不存在最小生成树如果最终得到的边数等于 n − 1 n-1 n−1 条则说明图中存在最小生成树。代码实现如下 int kruskal()
{int res 0, cnt 0; // res是最终最小生成树的长度cnt是全部循环结束以后所得生成树的边数for (int i 0; i m; i) // 图中总共有m条边{auto e edges[i]; // 先把这条边取出来int a e.a, b e.b, w e.w; // 找到边的两个顶点和边的权重// 看这两个顶点是不是在同一个并查集中if (find(a) ! find(b)) // 如果不在{p[find(a)] find(b); // 把a所在的并查集加入b所在的并查集相当于将两个并查集合并res w; // 累加上当前这条边的权重cnt; // 记录当前生成树中又多了一条边}}// 根据最终cnt的取值判断图中到底存不存在最小生成树if (cnt n - 1) return INF;else return res;
}二、完整代码实现
#include iostream
#include cstring
#include algorithm // sort()函数using namespace std;const int N 1e5 10, M 2e5 10, INF 0x3f3f3f3f;struct Edge
{int a, b, w;bool operator(const Edge e) const{return w e.w;}
}edges[M];int n, m;
int p[N];int find(int x)
{if (p[x] ! x) p[x] find(p[x]);return p[x];
}int kruskal()
{for (int i 1; i n; i) p[i] i;sort(edges, edges m);int res 0, cnt 0;for (int i 0; i m; i){auto e edges[i];int a e.a, b e.b, w e.w;if (find(a) ! find(b)){p[find(a)] find(b);res w;cnt;}}if (cnt n - 1) return INF;else return res;
}int main()
{cin n m;for (int i 0; i m; i){int a, b, w;scanf(%d%d%d, a, b, w);edges[i] {a, b, w};}int res kruskal();if (res INF) puts(impossible);else cout res endl;return 0;
}三、算法分析
Kruskal 算法的主要时间瓶颈在于对全部 m m m 条边的排序操作故该算法的时间复杂度为 O ( m log m ) O(m\log m) O(mlogm)Kruskal 算法主要用于求 稀疏图 的最小生成树问题 m n 2 mn^2 mn2。
【注】以上内容参考 AcWing。
