貪婪演算法應用：二分圖最小覆蓋問題與雙向鏈表桶優化實作

貪婪演算法應用：二分圖最小覆蓋問題與雙向鏈表桶優化實作

二分圖最小覆蓋問題 尋找集合 A 中最小子集 A'，使 B 中每個頂點至少與 A' 一個頂點相鄰。此問題為 NP-hard (可由集合覆蓋歸約)，貪婪啟發式在 O(n²) 或 O(n+e) 內給出近似解。本文詳細解析貪婪策略、資料結構設計 (雙向鏈表桶)、完整 C++ 實作與複雜度分析。

問題定義與貪婪策略

• 輸入**：二分圖 G = (A ∪ B, E)，|A| + |B| = n。
• 目標**：找最小 A' ⊆ A 覆蓋所有 B 頂點。
• 貪婪準則**：每步選擇覆蓋**最多未被覆蓋 B 頂點**的 A 頂點加入 A'。

範例演示

A = {1,2,3,16,17}, B = {4..15}。
初始 New[v] = degree(v)：New[1]=6, New[16]=6, New[3]=5, New[2]=4, New[17]=4。
步驟 1：選 16 (覆蓋 {5,6,8,12,14,15})。
步驟 2：更新 New，選 1 (覆蓋 {4,7,9,13})。
步驟 3：剩餘 {10,11}，選 17 (覆蓋 {4,9,10,11})。
結果 A' = {16,1,17} (大小 3)，恰為最小覆蓋。

資料結構設計：雙向鏈表桶

為在 O(1) 取得最大 New[v] 並支援 New[v]-- 後快速移動頂點：

• bin[k]：指向 New[v] = k 的頂點雙向鏈表頭。
• node[v].left/right：頂點 v 在鏈表中的前後指標；left 同時儲存當前桶編號。
• MaxBin：從 |B| 遞減掃描，首個非空桶即為最大值。

關鍵操作**：

// 將頂點 v 從舊桶移至新桶 toBin
void MoveBins(int bMax, int toBin, int v) {
    int l = node[v].left, r = node[v].right;
    // 從舊鏈表移除
    if (r) node[r].left = l;
    if (l > bMax || bin[l] != v) node[l].right = r;
    else bin[l] = r;
    // 插入新桶頭部
    if (toBin) {
        node[v].left = toBin;
        if (bin[toBin]) node[bin[toBin]].left = v;
        node[v].right = bin[toBin];
        bin[toBin] = v;
    }
}

完整演算法流程 (C++ 風格偽碼)

bool BipartiteCover(int L[], int C[], int &m) {
    // L[i]=1 表示 i∈A, L[i]=2 表示 i∈B
    int n = Vertices();
    int SizeOfA = count(L[i]==1), SizeOfB = n - SizeOfA;
    CreateBins(SizeOfB, n);           // 初始化桶
    int *New = new int[n+1];
    bool *Change = new bool[n+1];
    bool *Cov = new bool[n+1];
    LinkedStack S;

    // 初始化
    for (i=1..n) {
        Cov[i] = Change[i] = false;
        if (L[i]==1) {
            New[i] = Degree(i);       // 初始覆蓋數 = 度數
            InsertBins(New[i], i);
        }
    }

    int covered = 0, MaxBin = SizeOfB, m = 0;
    while (MaxBin > 0) {
        if (bin[MaxBin]) {            // 找到最大桶
            int v = bin[MaxBin];      // 取第一個頂點
            C[m++] = v;               // 加入覆蓋集
            // 標記 v 覆蓋的新頂點
            for (j = Begin(v); j; j = NextVertex(v)) {
                if (!Cov[j]) {
                    Cov[j] = true; covered++;
                    // 更新鄰接 j 的 A 頂點 New[k]--
                    for (k = Begin(j); k; k = NextVertex(j)) {
                        New[k]--;
                        if (!Change[k]) { S.Push(k); Change[k] = true; }
                    }
                }
            }
            // 批次移動頂點至正確桶
            while (!S.IsEmpty()) {
                S.Pop(k); Change[k] = false;
                MoveBins(SizeOfB, New[k], k);
            }
        } else MaxBin--;
    }
    DestroyBins(); delete[] New; delete[] Change; delete[] Cov;
    return covered == SizeOfB;
}

複雜度分析

桶優化關鍵**：New[v] 只遞減，每次最多移動一層桶，總移動次數 ≤ 邊數 e，故均攤 O(1)。

正確性與限制

• 若圖無覆蓋，演算法正確回傳 false (某 B 頂點度數為 0)。
• **不保證找到最小覆蓋** (NP-hard 問題)，但實驗顯示解品質通常接近最優。
• 可作為精確演算法 (分支限界、整數規劃) 的初始上界。

結語**：二分圖覆蓋貪婪演算法展示了「雙向鏈表桶」在動態最大值維護上的威力，實現 O(n+e) 近線性時間。此技巧廣泛應用於 Dijkstra (桶式優先佇列)、拓撲排序、流網路等演算法優化中。