Kruskal算法

用途

處理最小生成樹(MST)問題，即在給定的圖中求樹，使得這棵樹擁有圖中所有頂點，且所有邊都是圖中已知的邊，且滿足整棵樹的邊權之和最小。适用于邊少的稀疏圖。

算法描述

總體思路為：每次找到目前圖中未被選中的邊權最小的邊，如果邊的兩個頂點不在同一個連通塊中，那麼就把該邊加入到最小生成樹集合中。具體步驟如下：

1. 建立并維護一個并查集，用于判斷結點所屬連通塊；
2. 對圖中所有邊按邊權從小到大排序；
3. 依次選擇每條邊，判斷邊的頂點是否屬于同一連通塊，如果否則将該邊加入到最小生成樹中，如果是則不作處理；
4. 重複步驟3直到處理完所有邊，或是最小生成樹中的邊數已經達到 n - 1；
5. 判斷最小生成樹中的邊數，如果小于 n - 1，說明圖不連通，無解。

代碼實作

const int maxn = 1000;

struct edge
{
    int u, v;       // 邊頂點
    int cost;       // 邊權
};

edge E[maxn];       // 邊數組
int n, m;           // 結點數，邊數
int father[maxn];   // 并查集數組

bool cmp(edge a, edge b)        
{
    return a.cost < b.cost;     // 按照邊權從小到大排序
}

int findRoot(int x)             // 尋找根節點并壓縮路徑
{
    if (x == father[x])
        return x;
    
    int root = findRoot(father[x]);
    father[x] == root;
    return root;
}

int Kruskal()
{
    int sum = 0, numEdge = 0;       // 記錄邊權和，最小生成樹邊數
    
    for (int i = 0; i < n; i++)     // 初始化并查集數組
        father[i] = i;
    sort(E, E + m, cmp);            // 邊排序
    
    for (int i = 0; i < m; i++)
    {
        int rootU = findRoot(E[i].u);
        int rootV = findRoot(E[i].v);
        if (rootU != rootV)         // 頂點屬于不同連通塊，則将邊加入樹
        {
            father[rootU] = rootV;
            sum += E[i].cost;
            numEdge++;
            if (numEdge == n - 1)   // 邊數達到 n - 1 退出
                break;
        }
    }
    
    if (numEdge < n - 1)           // 邊數小于 n - 1，說明圖不連通，無解
        return - 1;
        
    return sum;                     // 傳回邊權和
}