演算法知識 - Maximum Bipartite Matching (使用 Augmenting Path Algorithm)

Maximum Bipartite Matching 介紹

在介紹最大二分匹配時，必須先介紹二分圖。
二分圖是一種圖的特例，二分圖的結構為，X 群體的每一個點都有連結到至少一個以上 Y 群體的點、T 群體的每一個點都有連結到至少一個以上 X 群體的點，且 X、Y 群體各自沒有邊互相連接。

圖源引用師大演算法

二分匹配就是，每一個 x 節點只能連到一個 y 個節點、每一個 y 節點只能連到一個 x 個節點，舊式二分匹配，類似於一夫一妻制。

圖源引用師大演算法

我們使用 Augmenting Path Algorithm 實作，時間複雜度為 \(O(VE)\)，V 是頂點、e 是邊

Augmenting Path Algorithm 證明與實作

證明

• 我們可以用 DFS，與三個陣列來解釋
  • mx[] x 每一個節點連接 y 的節點
  • my[] y 的每一個節點連接 x 的節點
  • vy[] 判斷 y 是否有被走過
• 我們知道 DFS 會走完所有的路程，因此我們對每一個 x 進行 dfs，如果 \(E(x,y)\)，且 y 沒有跟其他 x 點連接，那表示是一個匹配。
• 如果 y 有跟其他 x 點連接(定義 x’)，那我們只要讓 x’ 在找到下一個 y 點即可。
  • 如果找的到，那就新增一個最大匹配
  • 如果找不到，表示無法新增

原理

• 建立 mx[],my[],vy[]，並且有一個 edge[] vector，edge 為邊
• 將 mx[],my[]，設為 -1，表示沒有匹配節點
• 對每一個 x 節點進行 DFS
  • 如果 y 節點為 -1，那就新增匹配
  • 如果 y 節點配對 x’，檢查 x’，進行 DFS
• 如果沒有辦法匹配，輸出 false

參考連結

Maximum Bipartite Matching: Augmenting Path Algorithm by 師大演算法

心得

謝謝師大演算法幫助我這麼多，在北科學不太到的知識可以透過網路自學的方式學習，感謝你們！

Augmenting Path Algorithm 實作

不廢話，直接上來

vector<int> edge[MAXN];
int mx[MAXN], my[MAXN], vy[MAXN]; //matchX, matchY, visitY

bool dfs(int x){
    for(auto y: edge[x]){ //對 x 可以碰到的邊進行檢查
        if(vy[y] == 1) continue; //避免遞迴 error
        vy[y] = 1;
        if(my[y] == -1 || dfs(my[y])){ //分析 3
            mx[x] = y;
            my[y] = x;
            return true;
        }
    }
    return false; //分析 4
}

int bipartite_matching(){
    memset(mx, -1, sizeof(mx)); //分析 1,2
    memset(my, -1, sizeof(my));
    int ans = 0;

    for(int i = 1; i <= cnt; i++){  //對每一個 x 節點進行 DFS(最大匹配)
        memset(vy, 0, sizeof(vy));
        if(dfs(i)) ans++;

    }
    return ans;
}