最小生成樹——Kruskal

題目描述

給定一個n個點m條邊的無向圖，圖中可能存在重邊和自環，邊權可能為負數。

求最小生成樹的樹邊權重之和，如果最小生成樹不存在則輸出impossible。

給定一張邊帶權的無向圖G=(V, E)，其中V表示圖中點的集合，E表示圖中邊的集合，n=|V|，m=|E|。

由V中的全部n個頂點和E中n-1條邊構成的無向連通子圖被稱為G的一棵生成樹，其中邊的權值之和最小的生成樹被稱為無向圖G的最小生成樹。

算法思想

Kruskal算法，适用于稀疏圖的最小生成樹，時間複雜度 O ( m l o g m ) O(mlogm) O(mlogm)

1. 将所有邊按權值排序

2. 按權值從小到大周遊所有邊，使用并查集實作：

   如果邊的兩點不在同一集合中，則将它們納入到一個集合裡

   并累加集合中點的個數

3. 如果最終集合中點的個數$ != n$，說明不存在最小生成樹。

時間複雜度

Kruskal算法中需要将所有邊按權值從小到大排序，時間複雜度為 O ( m l o g m ) O(mlogm) O(mlogm)。然後按權值從小到大周遊所有邊，進行集合合并，因為使用并查集實作，時間複雜度約為 O ( m ) O(m) O(m)。

最終時間複雜度為 O ( m l o g m ) O(mlogm) O(mlogm)。

代碼實作

#include <bits/stdc++.h>
using namespace std;
const int N = 100010, M = 200010;

//p[i]表示結點i的祖宗結點的編号
int p[N];
int n, m;
struct edge{
    int a, b, w;
    //重載結構體的 < ，友善排序
    bool operator < (const edge & e) const
    {
        return w < e.w;
    }
}e[M];
int find(int x){
    if(p[x] != x){
        p[x] = find(p[x]); //找到并指派，路徑壓縮
    }
    return p[x];
}
int kruskal(){
    //res最小生成樹的邊權重之和
    //cnt最小生成樹集合中結點的個數，最初的集合隻有一個點
    int res = 0, cnt = 1;
    //按邊權值從小到大排序
    sort(e + 1, e + m + 1);
    for(int i = 1 ; i <= m ; i++){
        int a = e[i].a, b = e[i].b, w = e[i].w;
        //查找a和b的祖宗結點
        a = find(a), b = find(b);
        if(a != b) //a、b不在一個集合中
        {
            p[a] = b; //将a納入到b集合
            res += w; //最小生成樹的和增加w
            cnt ++; //最小生成樹中點的個數增加1
        }
    }
    if(cnt != n) return -1;
    else return res;
}
int main(){
    scanf("%d%d", &n, &m);

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

    for(int i = 1; i <= m; i ++){
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        e[i] = {a, b, w};
    }
    int t = kruskal();
    if(t == -1) puts("impossible");
    else printf("%d\n", t);
    return 0;
}