经典算法之Kruskal算法

电玩女神 2022-05-19 07:40 240阅读 0赞

# 作用： #

生成最小生成树，与prim算法不同的是，prim是以顶点为关键来生成最小树的，而Kruskal是以边为关键来生成最小数。

# 方法： #

1、将v个顶点，l条边的图G中所有的边按权值大小从小到大排序，这一步可以直接用库函数qsort或者sort。

2、从权值小的边开始依次选取，若选取的边使生成树T不形成回路，则选之；若选取的边使生成树形成回路，则将其舍弃；如此进行下去，直到选取v-1条边为止。

在上述的方法中，最关键的地方在于判断新加入的边与生成树是否构成回路，判断图是否构成回路有很多方法，这里我们使用[并查集][Link 1]来判断图是否构成回路。

### 并查集实现方法： ###

将顶点划分到不同集合中，每个集合中的顶点表示一个无回路的连通分量。算法开始时，将n个顶点划分到n个集合中，每个集合一个顶点，表示顶点之间互不相通。当选取一条边时，若它的两个顶点属于不同的集合，则表明连通了两个不同的连通分量，因每个连通分量没有回路，所以连通后仍然不会有回路，因此保留这条边；同时把两个集合进行合并成为一个集合。若选取的边属于同一个集合，则舍弃此边。

# 例题： #

我们以[HDU1863][]为例：

![70][]

### Sample Input： ###

3 3
    1 2 1
    1 3 2
    2 3 4
    
    1 3
    2 3 2
    
    0 100

### Sample Output： ###

3
    ?

# 实现代码： #

#include <iostream>
    #include <algorithm>
    using namespace std;
    
    #define N 5000
    
    /* father[x]表示x的父节点 */
    int father[N];
    /* rank1[x]表示x的秩 */
    int rank1[N];
    int v,l;    // v 顶点数 l 边数
    
    //定义结构体，用来存放图中的顶点，边和权值
    typedef struct Kruskal{
        int a,b,value;
    } Kruskal;
    //重载cmp，使Kruskal数组按权值的大小从 小——>大 排序
    bool cmp(const Kruskal & a, const Kruskal & b){
        return a.value < b.value;
    }
    //初始化father[]和rank1[],将n个顶点划分到n个集合中，每个集合一个顶点，表示顶点之间互不相通
    void ini(int size1){
        for(int i=1; i<=size1; i++)
        {
            father[i]=i;
            rank1[i]=0;
        }
    }
    //查找x的父节点
    int find1(int x){
        if(x!=father[x])
            father[x]=find1(father[x]);
        return father[x];
    }
    //合并节点x和y
    bool unions(int x,int y){
        int fx,fy;
        fx=find1(x),fy=find1(y);   //分别查找x，y的父节点
        if(fx==fy) return false;   //当两个节点的父节点相同时，则不用合并
        else if(rank1[fx] >= rank1[fy]){   //以下操作均为合并节点
            father[fy] = fx;
            rank1[fx] += rank1[fy];
        }
        else{
            father[fx] = fy;
            rank1[fy] += rank1[fx];
        }
        return true;
    }
    int main()
    {
            //边值和
                   //权值和
                        //循环终止条件
        int ltotal,sum,flag;
        while(cin>> l >> v && l){
            //定义结构体G
            Kruskal G[N];
            ltotal=0,sum=0,flag=0;
            //初始化集合
            ini(v);
            //输入
            for(int i=1; i<=l; i++)
                cin >> G[i].a >> G[i].b >> G[i].value;
            //排序
            sort(G+1,G+1+l,cmp);
            for(int i=1; i<=l; i++){
                if(unions(G[i].a,G[i].b)){
                    ltotal++;
                    sum+=G[i].value;
                    //cout<<G[i].a<<"--"<<G[i].b<<endl;
                }
                //如果生成树中已有v-1条边则终止循环
                if(ltotal==v-1){
                    flag=1;
                    break;
                }
            }
            if(flag)
                cout << sum << endl;
            else
               cout << "?" << endl;
        }
        return 0;
    }

# 运行结果： #

![70 1][]

[Link 1]: https://baike.baidu.com/item/%E5%B9%B6%E6%9F%A5%E9%9B%86/9388442?fr=aladdin
[HDU1863]: http://acm.hdu.edu.cn/showproblem.php?pid=1863
[70]: /images/20220519/7a10efd105d94854b904c967452f0fc5.png
[70 1]: /images/20220519/a10bbe9f790d4632b79f0fa732b7eec8.png