大学IT网 - 最懂大学生的IT学习网站! QQ资料交流群:367606806
当前位置:大学IT网 > C++技巧 > 图算法 最小生成树 Kruskal算法(并查集)

图算法 最小生成树 Kruskal算法(并查集)

关键词:最小生成树Kruskal算法  阅读(777) 赞(12)

[摘要]本文是对图算法 最小生成树 Kruskal算法(并查集)的讲解,对学习C++编程技术有所帮助,与大家分享。

一、介绍

  由于忙于各类事务,在算法方面的学习有所停滞,现在将求最小生成树的另外一种算法补上,也就是Kruskal算法。有关最小生成树算法正确性的证明见上面链接。

  Kruskal算法是一种实现起来较为简单,比较容易理解的算法,在图较为稀疏时能够获得很好的性能,但当图较为稠密时(|E|>>|V|)性能便不如Prim算法。后面我们会根据实际代码对Kruskal算法的时间复杂度进行分析。

  Krusksl算法采用并查集(算法导论上的表示为不相交集合)实现。初始时,我们的所有顶点都构成单独的一棵树,也就是说由|V|棵树组成的森林。算法首先要做的是,将所有的边,按权值大小进行非降序排列。然后,按照权值从小到大来选择边,若该边的两个端点不在一棵树中,则将他们合并,并将该边置于最小生成树中。一直访问完所有的边为止。可以看出Kruskal算法属于一种贪心算法,而且能保证找到全局最优解。算法理解相应简单,我们不给出相应的证明,有兴趣的可以去钻研一下算法导论。

二、伪代码

  算法的伪代码如下,其中A保存最小生成树,MAKE-SET(v)表示构造一棵只有顶点v的树,FIND-SET(u)表示找u所在树的根节点,Union(u, v)表示合并u和v的所在树:

    MST-KRUSKAL(G, W)

      A←∅

      for each vertex v∈V[G]

        do MAKE-SET(v)

      sort the eages of E into nondecreasing order by weight w

      for each eage(u, v)∈E, teken in nondecreasing order by weight

        do if(FIND-SET(u)≠ FIND-SET(v))

          then A←A∪{ (u, v) }

            Union(u, v)

    return A

三、实现

下面给出C++的实现,之后再来分析时间复杂度:

 #include <iostream>
 #include <cstdio>
 #include <algorithm>
 #include <cstring>
 using namespace std;
 
 #define maxn 110    //最多点个数
 int n, m;   //点个数,边数
 int parent[maxn];   //父亲节点,当值为-1时表示根节点
 int ans;    //存放最小生成树权值
 struct eage     //边的结构体,u、v为两端点,w为边权值
 {
     int u, v, w;
 }EG[5010];
 
 bool cmp(eage a, eage b)    //排序调用
 {
     return a.w < b.w;
 }
 
 int Find(int x)     //寻找根节点,判断是否在同一棵树中的依据
 {
     if(parent[x] == -1) return x;
     return Find(parent[x]);
 }
 
 void Kruskal()      //Kruskal算法,parent能够还原一棵生成树,或者森林
 {
     memset(parent, -1, sizeof(parent));
     sort(EG+1, EG+m+1, cmp);    //按权值将边从小到大排序
     ans = 0;
     for(int i = 1; i <= m; i++)     //按权值从小到大选择边
     {
         int t1 = Find(EG[i].u), t2 = Find(EG[i].v);
         if(t1 != t2)    //若不在同一棵树种则选择该边,合并两棵树
         {
             ans += EG[i].w;
             parent[t1] = t2;
         }
     }
 }
 int main()
 {
     while(~scanf("%d%d", &n,&m))
     {
         for(int i = 1; i <= m; i++)
             scanf("%d%d%d", &EG[i].u, &EG[i].v, &EG[i].w);
         Kruskal();
         printf("%d\n", ans);
     }
     return 0;
 }

四、时间复杂度

  分析以上代码中Kruskal算法的时间复杂度,n用V表示,m用E表示:

  29行:将V个点父节点都置为-1,时间为O(V)

  30行:stl中的sort函数,头文件为#include <algorithm>,时间复杂度为O(E log E)

  32-40行:由于FIND-SET是树搜索操作,平均时间复杂度为O(lg V),因为这几行时间复杂度平均为O(E log V)

综上:总复杂度表示为:O(V) +O(E log E) +O(E log V);

  当图为稠密图时,时间复杂度可表示为O(E log E);

  一般图基本为稀疏图|E| < |V|^2,时间复杂度可表示为O(E log V)。

  因而,从时间复杂度来看,当图为稀疏图时,Kruskal算法性能和Prim相当,当为稠密图时,Prim性能更好。

五、小技巧

  注意每合并两棵树,树的棵树就减少1,当根节点的个数只有一个即只有一棵树时,说明生成了最小生成树,此时程序便可终止,没有必要去查看后面权值更大的边,因而判断根节点的数目,在图较为稠密时,能够提高一定的性能,代码修改如下,图为完全图:

 #include <iostream>
 #include <cstdio>
 #include <algorithm>
 #include <cstring>
 using namespace std;
 
 #define maxn 110    //最多点个数
 int n, m;   //点个数,边数
 int parent[maxn];   //父亲节点,当值为-1时表示根节点
 int ans;    //存放最小生成树权值
 struct eage     //边的结构体,u、v为两端点,w为边权值
 {
     int u, v, w;
 }EG[5010];
 
 bool cmp(eage a, eage b)    //排序调用
 {
     return a.w < b.w;
 }
 
 int Find(int x)     //寻找根节点,判断是否在同一棵树中的依据
 {
     if(parent[x] == -1) return x;
     return Find(parent[x]);
 }
 
 void Kruskal()      //Kruskal算法,parent能够还原一棵生成树,或者森林
 {
     memset(parent, -1, sizeof(parent));
     int cnt = n;        //初始时根节点数目为n个
     sort(EG+1, EG+m+1, cmp);    //按权值将边从小到大排序
     ans = 0;
     for(int i = 1; i <= m; i++)     //按权值从小到大选择边
     {
         if(cnt == 1) break;     //当根节点只有1个时,跳出循环
         int t1 = Find(EG[i].u), t2 = Find(EG[i].v);
         if(t1 != t2)    //若不在同一棵树种则选择该边,
         {
             ans += EG[i].w;
             parent[t1] = t2;
             cnt--;      //每次合并,减少一个根节点
         }
     }
 }
 int main()
 {
     while(scanf("%d", &n), n)
     {
         m = n*(n-1)/2;  //完全图
         for(int i = 1; i <= m; i++)
             scanf("%d%d%d", &EG[i].u, &EG[i].v, &EG[i].w);
         Kruskal();
         printf("%d\n", ans);
     }
     return 0;
 }


相关评论