最小生成树(Minimum Spanning Tree)——Prim算法与Kruskal算法+并查集

最小生成树——Minimum Spanning Tree，是图论中比较重要的模型，通常用于解决实际生活中的路径代价最小一类的问题。我们首先用通俗的语言解释它的定义：

对于有n个节点的有权无向连通图，寻找n-1条边，恰好将这n个节点相连，并且这n-1条边的权值之和最小。

对于MST问题，通常常见的解法有两种：Prim算法或者 Kruskal算法+并查集

对于最小生成树，一定要注意其定义是在无向连通图的基础上，如果在有向图中，那么就需要另外的分析，单纯用无向图中的方法是不能得出正确解的，这一点我在比赛中确实吃过亏

好了，进入正题：

Prim算法：（基于点的贪心思路）由于是基于点的算法，因此适合于稠密图，一下给出代码没有经过堆优化，时间复杂度为O(N^2)

　　记原图为G，生成树图为MST，其中G的节点个数为n个

　　算法描述如下：

任取G中的一点，加入MST中——这一步的作用是选择一个节点作为整个算法的起点
采用贪心策略，将刚刚加入的节点记为u，以u为中心，检查与u相连且没有加入MST的节点（未访问过的节点），选择权值最小的边，如果有多条边的权值均最小，则任取一条边。——贪心策略，选择局部最优
将所选择的边中，不在MST中的那个节点，加入MST——举例来说，比如（u，v）是当前与u相连，v不再MST中，且权值最小的边，则边（u，v）被选中，并将v加入MST。
如果步骤2-3被执行了n-1次，则退出，反之则返回到步骤2。——由于Prim算法初始化时加入了起点，而步骤2-3每执行一次都会加入一个新的节点，所以只需判断执行次数。

关于算法的正确性证明网上都有证明，这里就不再赘述。

 //inf为路径权上界，maxn为图的临接矩阵的点数

 //vis是记录是否访问过，cost[i]记录到达第i个节点的最小代价

 const int inf=0x7fffffff,maxn=;

 int G[maxn][maxn],vis[maxn],cost[maxn],n;

 //len为MST长度

 int prim(){

     memset(vis,,sizeof(vis));

    //加入起始节点

     int pos=,min=inf,len=,cnt=n;

     vis[]=;

     for(int v=;v<=n;v++)cost[v]=G[pos][v];

    //加入剩余n-1个节点

     while(--cnt){

         for(int i=;i<=n;i++)if(!vis[i]&&cost[i]<min){

             pos=i;min=cost[i];

         }

         len+=min;vis[pos]=;

         //以新加入的节点为中心，更新权值信息

         for(int i=;i<=n;i++)if(!vis[i]&&G[pos][i]<cost[i])

             cost[i]=G[pos][i];

         min=inf;

     }

     return len;

 }

结合poj上的一道水题来验证一下Prim的威力吧~亲测156k内存0ms过（C++编译器）

poj1258：http://poj.org/problem?id=1258

Kruskal算法：（基于边的贪心算法）基于边的贪心，由图的性质不难知道，当图为稠密图时，边的数目远大于点的数目，因此Kruskal+并查集适用于稀疏图

将所有的边按权值由小到大排序——准备工作，可借助sort（）完成，但是在工程中，如果不知道边和点的数量关系，还是应该用最小值堆，而不是sort来保证效率，但在竞赛中，sort足够了
从非MST中的边中寻找一条，在不会与现有的MST构成环的前提下，权值最小的边，加入MST
如果已经加入了n-1条边，则结束，否则返回步骤2

那么从算法描述，我们不难看到，整个算法中的核心部分是，判断当前权值最小的边是否会与MST构成环。

那么如何实现这个判断呢？一种思路是我们通过BFS或者DFS，用遍历图的办法来判断——然而这个编程复杂度和时间复杂度都很高╮(╯-╰)╭

我们可以从另一个角度进行考量。如果说我们给每个MST一个代表元素（representative），或者说，是一个标记，那么，对于一个不连通的无向图，每个MST就可以看作一个连通支，而每个连通支其实可以看作一个集合，连通支中的节点就是集合中的元素，而我们只关心一个新的元素是否在原先的集合中。

那么判定元素是否在集合中，我们是不是马上想到了一种树形结构——并查集（Union-Find Set）。

并查集的数组实现如下：p[x]表示第x元素的父元素，我们规定当p[x]==x时，表示找到了这一组元素的代表元（representative），

则可以递归的进行查找，并同时进行路径压缩，因此，不难看出，在均摊意义下，并查集的时间复杂度为O(1)。

 int find(int x){ return p[x]== x ? x : p[x] = find(p[x]); }

为什么return语句可以这样和赋值语句连用？

大家想想诸如a=b=c=1;这样的连续赋值，不难理解，其实赋值语句是有返回值的，并且返回值为左值的值，即先返回c的值1，赋给b，返回b的值1，赋给a，最后返回a的值。

这样，我们就可以给出kruskal的完整实现了：

 const int maxn=;

 //n为节点个数，m为边个数,r存储第i+1小的边的序号，w存储第i条边的权值，u和v存储第i条边的节点序号

 int p[maxn],n,u[maxn],v[maxn],w[maxn],r[maxn],m;

 //并查集find

 int find(int x){ return p[x]==x?x:p[x]=find(p[x]); }

 //间接排序函数

 int cmp(const int i,const int j){ return w[i]<w[j]; }

 int kruskal(){

     int len=;

     for(int i=;i<n;i++)p[i]=i;//初始化并查集

     for(int i=;i<m;i++)r[i]=i;//初始化边的序号

     sort(r,r+m,cmp);//<algorithm>中的优化的快排

     for(int i=;i<m;i++){

         int e=r[i],x=find(u[e]),y=find(v[e]);

         if(x!=y){ len+=w[e];p[y]=x; }//并查集Union

     }

     return len;

 }

不难看出，Kruskal算法的复杂度为O(ElogE)，基本上都集中在排序了，所以，工程上还可以用优先队列或者斐波那契堆来减小复杂度

这样，无向图中的MST模型就介绍的差不多了，通常这个模型会用于解决资源最省之类的问题，不过，kruskal还没有实践过，所以，有时间我再更新一些相关习题吧~

秒客网

最小生成树(Minimum Spanning Tree)——Prim算法与Kruskal算法+并查集

相关文章