克鲁斯卡尔算法

kruskal算法一般指本词条

Kruskal算法是一种用来查找最小生成树的算法，由Joseph Kruskal在1956年发表。用来解决同样问题的还有Prim算法和Boruvka算法等。三种算法都是贪心算法的套用。和Boruvka算法不同的地方是，Kruskal算法在图中存在相同权值的边时也有效。

基本介绍

中文名：克鲁斯卡尔算法 外文名：Kruskal algorithm 套用领域：运筹学 时间複杂度：O(|E|log|E|)

基本思想

先构造一个只含 n 个顶点、而边集为空的子图，把子图中各个顶点看成各棵树上的根结点，之后，从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，即把两棵树合成一棵树，反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直到森林中只有一棵树，也即子图中含有 n-1 条边为止。

步骤

新建图G，G中拥有原图中相同的节点，但没有边； 将原图中所有的边按权值从小到大排序； 从权值最小的边开始，如果这条边连线的两个节点于图G中不在同一个连通分量中，则添加这条边到图G中； 重複3，直至图G中所有的节点都在同一个连通分量中。

证明

这样的步骤保证了选取的每条边都是桥，因此图G构成一个树。 为什幺这一定是最小生成树呢？关键还是步骤3中对边的选取。算法中总共选取了n-1条边，每条边在选取的当时，都是连线两个不同的连通分量的权值最小的边 要证明这条边一定属于最小生成树，可以用反证法：如果这条边不在最小生成树中，它连线的两个连通分量最终还是要连起来的，通过其他的连法，那幺另一种连法与这条边一定构成了环，而环中一定有一条权值大于这条边的边，用这条边将其替换掉，图仍旧保持连通，但总权值减小了。也就是说，如果不选取这条边，最后构成的生成树的总权值一定不会是最小的。

时间複杂度

平均时间複杂度为O(|E|log|E|)，其中E和V分别是图的边集和点集。

C语言程式

#include<stdio.h>#include<iostream>#include<algorithm>using namespace std;const int M = 1e5+7;struct node{  int a,b,val;} Q[M];int fa[M];int Rd(){  int res=0;char c;  while(c=getchar(),!isdigit(c));  do {    res=(res<<3)+(res<<1)+(c^48);  } while(c=getchar(),isdigit(c));  return res;}bool cmp(LZ a,LZ b){  return a.val<b.val;}int getfa(int v){    if(fa[v]!=v)fa[v]=getfa(fa[v]);    return fa[v];}int main(){    int i,j,n,m,x,y;    scanf("%d%d",&n,&m);    for(i=1;i<=m;i++)    {        Q[i].a=Rd();Q[i].b=Rd();Q[i].val=Rd();    }    sort(Q+1,Q+m+1,cmp);    for(i=1;i<=n;i++)    {        fa[i]=i;    }    int sum=0,cut=0;    for(i=1;i<=m;i++)    {        x=getfa(Q[i].a);        y=getfa(Q[i].b);                if(x==y)continue;                sum+=Q[i].val;                if(++cut==n-1)break;                fa[x]=y;        }        printf("%d",sum);        return 0;}