KruskalAlgorithm克鲁斯卡尔算法

Kruskal

首先 我们约定 n为节点数，m为边数

一、概念

Kruskal算法主要用于解决Minimum Spanning Trees(最小生成树)问题。

二、基本思想

先选择权值较小的边，检查是否存在回路，然后继续选择，直到选择了 n − 1 n-1 n−1 的边结束。

三、模板代码

const int N=1005;//Nodes Countconst int M=2010;//Edges Countint p[N];//p[i]记录节点 i 的父节点int n;//顶点数int res=0;struct Edge{ int a;//Start Point of the edge int b;//End Point of the edge int v;//The Value of the edge}edge[M];int find(int x)//找到x的父节点{ return p[x]==x ? x : p[x]=find(p[x]); //等价于以下代码 }void merge(int x,int y)//将含x,y的两个集合合并成一个集合{ p[find(x)]=find(y);}bool cmp(Edge x,Edge y)//排序函数{ return x.v

四、实例题目

【习题】【最小生成树习题】LaoQiao C/C++ Group B 2020.4 9.通电
仅部分习题，若想了解更多习题请关注微信公众号或者博客。

---

如有疑问欢迎在评论区留言或者通过Email联系我

My Email:Wizzy-Ang@qq.com

欢迎大家关注我的个人公众号WizzyAngShare，(还有个人博客)

我会在这里分享编程语言语法，算法，及区块链的相关知识，还有各种奇奇怪怪的小知识等着你~

虽然现在这个公众号有亿点草率 ，我会努力更新的~~~