Kruskal算法1、配置文件Kruskal算法是用于寻找最小生成树(M S T MST MST )的算法，1956年由Joseph Kruskal发表。 求解最小生成树的算法通常有两种： Kruskal算法和Prim算法。 这里介绍Prim算法的详细Blog。 https://blog.csdn.net/hzf 0701/article/details/107927858。 与Prim算法不同，该算法的中心思想是合并点，而Prim算法的中心思想是合并点。 这里将在以后的实现过程中看到。
2、假设构造过程连通网n=(v，e ) n=(v，e ) n=(v，e ) n=(v，e )，将N N N中的边按权重从小到大的顺序排列。
初始状态为只由nn个顶点终止的非连通图t=(v，{ } ) t=(v，{ } ) v，} ) t=(v，{ } )，图中的各顶点具有一个连通分量。
E E E中选择权值最小的边，如果该边所属的顶点在T T T中的不同连接分量上，即未形成环，则将该边放入T T T，否则舍弃该边，选择权重值次最小的边。
重复，直到T T T的所有顶点达到相同的连通分量。
该算法的结构过程非常简洁明了，为什么这种结构过程能形成最小生成树？ 让我们来看看第二步。 选定边的顶点是不同的连接分量，由于边的权重最小，因此确保参与的边在T T T上没有循环，权重也最小。 这样，最后，当所有的连接分量相同时，即所有的顶点都在生成树中成功连接时，我们构成的树成为最小生成树。
3、范例
4、算法实现步骤：
按权重从小到大的顺序对存储边的数组temp进行排序，注意运算符的重载。
初始化连通分配列v e r x verx verx。
依次查看数组temp的边，在循环中执行以下操作。
从按顺序排列的排列temp到边(u、v ) ) u、v ) ) u、v )； 在v
e r x verx verx中分别查找 u u u和 v v v所在的连通分量 v 1 和 v 2 v_1和v_2 v1和v2，进行判断。 如果 v 1 v_1 v1和 v 2 v_2 v2不等，说明所选的两个顶点分别属于不同的连通分量，则将此边存入最小生成树 t r e e tree tree，并合并 v 1 v_1 v1和 v 2 v_2 v2这个两个连通分量。如果 v 1 v_1 v1和 v 2 v_2 v2相等，则说明所选的两个顶点属于同一个连通分量，舍去此边而选择下一条权值最小的边。 /**邮箱：unique_powerhouse@qq.com*blog:https://me.csdn.net/hzf0701*注：文章若有任何问题请私信我或评论区留言，谢谢支持。**/#include<bits/stdc++.h>//POJ不支持#define rep(i,a,n) for (int i=a;i<=n;i++)//i为循环变量，a为初始值，n为界限值，递增#define per(i,a,n) for (int i=a;i>=n;i--)//i为循环变量， a为初始值，n为界限值，递减。#define pb push_back#define IOS ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)#define fi first#define se second#define mp make_pairusing namespace std;const int inf = 0x3f3f3f3f;//无穷大const int maxn = 1e5;//最大值。typedef long long ll;typedef long double ld;typedef pair<ll, ll> pll;typedef pair<int, int> pii;//*******************************分割线，以上为自定义代码模板***************************************//struct edge{int s;//边的起始顶点。int e;//边的终端顶点。int w;//边权值。bool operator < (const edge &a){return w<a.w;}};edge temp[maxn];//临时数组存储边。int verx[maxn];//辅助数组，判断是否连通。edge tree[maxn];//最小生成树。int n,m;//n*n的图，m条边。int cnt;//统计生成结点个数，若不满足n个，则生成失败。int sum;//最小生成树权值总和。void print(){//打印最小生成树函数。cout<<"最小生成树的权值总和为："<<sum<<endl;rep(i,0,cnt-1){cout<<tree[i].s<<" "<<tree[i].e<<"边权值为"<<tree[i].w<<endl;}}void Kruskal(){rep(i,1,n)verx[i]=i;//这里表示各顶点自成一个连通分量。cnt=0;sum=0;sort(temp,temp+m);//将边按权值排列。int v1,v2;rep(i,0,m-1){v1=verx[temp[i].s];v2=verx[temp[i].e];if(v1!=v2){tree[cnt].s=temp[i].s;tree[cnt].e=temp[i].e;tree[cnt].w=temp[i].w;//并入最小生成树。rep(j,1,n){//合并v1和v2的两个分量，即两个集合统一编号。if(verx[j]==v2)verx[j]=v1; //默认集合编号为v2的改为v1.}sum+=tree[cnt].w;cnt++;}}//结束双层for循环之后得到tree即是最小生成树。print();}int main(){//freopen("in.txt", "r", stdin);//提交的时候要注释掉IOS;while(cin>>n>>m){int u,v,w;rep(i,0,m-1){cin>>u>>v>>w;temp[i].s=u;temp[i].e=v;temp[i].w=w;}Kruskal();}return 0;} 5、算法分析对于有 m m m条边和 n n n个顶点的图。在 f o r for for循环中最耗时的操作就是合并两个不同的连通分量，第一个循环语句的频度为 m m m，第二个循环由于存在 i f if if语句，所以平均频度是 l o g 2 n log_2n log2n，所以该算法的平均时间复杂度为 O ( m l o g 2 n ) O(mlog_2n) O(mlog2n)，故和Prim算法相比，此算法适合用于稀疏图。
6、测试以示例数据为测试样例：
7 111 2 71 4 52 4 92 3 82 5 74 5 154 6 66 7 115 6 85 7 93 5 5测试结果如图：