【算法】图论_最小生成树(MST)_Kruskal

最小生成树（MST），即最小权值生成树，一般是无向图中的概念。

生成树是原图的这样一个子图

没有回路，即n个点最多有n-1条边
所有点连通，这下好了，最少也要有n-1条边

正是因为它无向无环连通，所以被称为一棵树。而MST是所有生成树中，边的权值和最小的那一棵。

原图 MST

求解MST常用两个算法，Prim和Kruskal，两者都是贪心的思想，今天我们先来说说Kruskal。

过程：

先描述一遍算法的过程：

将所有边按权值由小到大排序；
从小到大考察每一条边——目前加入这条边会形成环吗？不会，则向当前子图中加入这条边，会，则不加入，考察下一条边；
加入n-1条边之后，得到的子图即MST，算法完成。

【算法】图论_最小生成树(MST)_Kruskal

按照顺序，加入红色的边会形成环，舍去

证明：

既然Kruskal算法是基于贪心的，我们就得证明它的正确性。

首先，我们先证明按照Kruskal的流程，找出来的子图一定是一棵生成树。假设不是生成树，那么这个子图要么有环，要么不

连通。

不会有环，因为考察每条边时，判定条件就是不会形成环；
一定连通，n个点，n-1条边，还是简单图，所以一定连通；

接下来，我们再证明这棵树就是我们要找的MST。

我们使用反证法，我们找到的生成树不是MST，那么至少存在一棵生成树的权值和小于当前的，并且我们肯定选错了一条边

（那条边被我们舍弃了）！而我们考察一条边的时候，只排除了会形成环的边。

现在假设我们加入了一条会形成环的边e，会使最终的权值和更小。由于我们最终需要一棵生成树，所以得在这个环上删除一

条边（不能形成环），那么该删哪一条呢？我们发现，环上的任何一条边都不会比e的权值更大（因为我们是按边权从小到大

顺序加入的），即加入这条边不会使权值变小，与假设矛盾，所以按照之前的策略，得到的就是MST。

复杂度：

算法由排序，和判断是否形成环两部分组成，如果使用快排+并查集的话，还是比较能接受的。

实现：

现在问题来了，我们怎么方便的表示加入这条边后，子图会不会形成环？这个时候，我们就需要用并查集这个神奇的东西了。

现在把每一条边想象成一条命令，加入这条边即把边的两个端点所在的集合合并。而如果没有加入这条边之前，两个端点已经

在一个集合里了，那么说明加入这条边会形成环。

下面是具体代码：

#include<stdio.h>
#include<stdlib.h>
typedef struct
{
  int l,r,data;
} edge;

int father[10000],ans=0;
edge e[10000];

int findfather(int x)
{
    if (father[x]==x) return x;
    else returnfather[x]=findfather(father[x]); //路径压缩
}
void unionset(int x, inty)
{
    int fx=findfather(x);
    int fy=findfather(y);
    //这里有另外一个优化没有写出，在合并时比较两个集合树的深度（rank）,防止树过深。
    father[fx]=fy;
}
int comp(const void*a,const void *b)
{
  return(*(edge*)a).data>(*(edge*)b).data?1:-1;
}

int main()
{
  int i,n; //n条边
  for (i=1; i<=10000; i++)
    father[i]=i;

  scanf("%d",&n);
  for (i=1; i<=n; i++)
   scanf("%d%d%d",&e[i].l,&e[i].r,&e[i].data);

  qsort(e,n,sizeof(e[1]),comp);

  for (i=1; i<=n; i++)
  {
    int fl=findfather(e[i].l);
    int fr=findfather(e[i].r);
    if (fl!=fr)
    {
      unionset(fl,fr);
      ans+=e[i].data;
    }
  }
}

秒客网

【算法】图论_最小生成树(MST)_Kruskal

相关文章