最小生成樹算法：Kruskal 與 Prim 實現詳解

問題重述

給定無向圖的邊列表（二元組），求最小生成樹（MST），輸出構成 MST 的邊集合。要求 Java 或 C# 實現，確保無環且連通所有節點。

算法選型

本題輸入為邊列表，Kruskal 更自然。

Kruskal 算法步驟

1. 將所有邊按權重升序排序（本題無權重，視為同權，任意序）。
2. 初始化并查集，每個節點自成一棵樹。
3. 遍歷邊：若兩端點屬於不同集合，合併並加入 MST；否則跳過（成環）。
4. 當 MST 邊數 = 節點數 - 1 時結束。

C# 完整實現

using System;
using System.Collections.Generic;
using System.Linq;

public class MSTSolver
{
    public static List<Tuple<string, string>> Kruskal(List<Tuple<string, string>> edges)
    {
        // 1. 收集所有節點
        var nodes = edges.SelectMany(e => new[] { e.Item1, e.Item2 }).Distinct().ToList();
        var nodeToIdx = nodes.Select((n, i) => new { n, i }).ToDictionary(x => x.n, x => x.i);
        
        // 2. 并查集
        int[] parent = Enumerable.Range(0, nodes.Count).ToArray();
        int[] rank = new int[nodes.Count];
        
        int Find(int x) => parent[x] == x ? x : parent[x] = Find(parent[x]);
        void Union(int a, int b)
        {
            a = Find(a); b = Find(b);
            if (a == b) return;
            if (rank[a] < rank[b]) parent[a] = b;
            else if (rank[a] > rank[b]) parent[b] = a;
            else { parent[b] = a; rank[a]++; }
        }
        
        // 3. 處理邊（無權重，保持輸入順序或字典序）
        var mst = new List<Tuple<string, string>>();
        foreach (var e in edges)
        {
            int u = nodeToIdx[e.Item1], v = nodeToIdx[e.Item2];
            if (Find(u) != Find(v))
            {
                Union(u, v);
                mst.Add(e);
                if (mst.Count == nodes.Count - 1) break;
            }
        }
        return mst;
    }
}

// 使用示例
var input = new List<Tuple<string, string>> 
{ 
    Tuple.Create("a","b"), Tuple.Create("a","c"), Tuple.Create("b","c") 
};
var result = MSTSolver.Kruskal(input);
result.ForEach(e => Console.WriteLine($"({e.Item1},{e.Item2})"));

Java 完整實現

import java.util.*;

public class MSTSolver {
    public static List<String[]> kruskal(List<String[]> edges) {
        // 節點映射
        Map<String, Integer> id = new HashMap<>();
        int idx = 0;
        for (String[] e : edges) {
            for (String s : e) if (!id.containsKey(s)) id.put(s, idx++);
        }
        
        // 并查集
        int[] parent = new int[idx];
        int[] rank = new int[idx];
        for (int i = 0; i < idx; i++) parent[i] = i;
        
        int find(int x) { return parent[x] == x ? x : (parent[x] = find(parent[x])); }
        void union(int a, int b) {
            a = find(a); b = find(b);
            if (a == b) return;
            if (rank[a] < rank[b]) parent[a] = b;
            else if (rank[a] > rank[b]) parent[b] = a;
            else { parent[b] = a; rank[a]++; }
        }
        
        List<String[]> mst = new ArrayList<>();
        for (String[] e : edges) {
            int u = id.get(e[0]), v = id.get(e[1]);
            if (find(u) != find(v)) {
                union(u, v);
                mst.add(e);
                if (mst.size() == id.size() - 1) break;
            }
        }
        return mst;
    }
    
    public static void main(String[] args) {
        List<String[]> input = Arrays.asList(
            new String[]{"a","b"}, new String[]{"a","c"}, new String[]{"b","c"}
        );
        kruskal(input).forEach(e -> System.out.println("(" + e[0] + "," + e[1] + ")"));
    }
}

關鍵細節

• 節點去重：輸入可能包含孤立節點，需先收集所有節點。
• 并查集優化：路徑壓縮 + 按秩合併，近乎 O(1)。
• 無權重處理：題目未給權重，按輸入順序或字典序選邊均可，結果可能不唯一但均為合法 MST。
• 斷圖判斷：若最終 MST 邊數 < 節點數 - 1，說明原圖不連通，需拋出異常或返回空。

測試用例

// 三角形：任選兩邊
Input: (a,b) (a,c) (b,c)
Output: (a,b) (a,c)  // 或其他任意兩邊

// 方形+對角線
Input: (1,2) (2,3) (3,4) (4,1) (1,3)
Output: (1,2) (2,3) (3,4)  // 權重相同時按序選前三條

總結

Kruskal 算法配合并查集是解決「邊列表求 MST」的標準利器。C# 與 Java 實現核心邏輯一致，差異僅在語法糖與集合庫。掌握并查集模板，即可輕鬆應對各類生成樹、連通分量、動態連通性問題。