演算法知識 - Graph theorm Find Bridge

Find Bridge 介紹

Find Bridge 顧名思義就是要找到橋，那這裡的橋是甚麼意思呢？
想想現實生活中的橋，是不是只要橋斷開了兩邊的聯繫就斷了？

那麼圖論中亦是如此，只要有一個邊斷掉了，那麼就一張圖就被分成兩個圖了！(注意，兩張圖中可能其中有一張圖只有一個點)
師大演算法中有用圖片進行說明，其中我用紅筆圈出來的就是橋。
注意，圖中的 (1,2)、(7,8)、(7,9) 都是橋

而此演算法解出的問題就是讓所有這些橋的點都被找到

參考連結

• 她講得很好，大力推薦 Finding bridges in a graph in O(N+M) by CP-alhorithm
• 師大演算法

  邏輯證明

• 四個陣列，一個 vector edge 紀錄題目的邊
  • depth 記錄當前深度
  • low 紀錄當前節點，能返回的最淺深度是多少
  • visit 紀錄是否有走訪過
  • ancestor 為 disjoint set，將所有橋的節點放在一起
• 程式邏輯與證明
  • 首先我們先假設 low[root] = depth[root]，完全一樣
  • 當 root 可以返回到已經走訪過的邊(定義 v)時，此時 depth[root] < depth[v]
    因為可以碰到之前走訪過的點，因此這個邊不會是一個 bridge，root 就也不會是 bridge node
  • 當 low[root] > low[v] 表示 v 這個節點他可以返回到更前面的節點。因此就表示 root 也不是 bridge node。
  • 當 low[v] > depth[root]，表示 root 的下一個節點 v，沒辦法透過任何方式回到 root 身邊來，因此我們就可以證實 root 跟 v 都是 bridge node，有一個 bridge node。
    • 此時，將 root 與 v 放入同一個 bridge node set，就可以知道他們都是 bridge node。

程式碼說明

這裡我們透過程式碼說明，並且解釋。

#define MAXN
vector<int> edge[MAXN];
int visit[MAXN], depth[MAXN], low[MAXN];
int ancestor[MAXN];
int cnt = 1

int find_root(int x){ 
    if(ancestor[x] != x) return ancestor[x] = find_root(ancestor[x]);
    return ancestor[x];
}

void find_bridge(int root, int past){ //找到橋點
    visit[root] = 1; //表示走訪過
    depth[root] = low[root] = cnt++; //邏輯證明 2.1
    for(int node: edge[root]){ //不斷遍地
        //因為是無向邊，因此雙向同個 edge 不是 bridge 
        if(node == past) continue; 
        if(visit[node]) low[root] = min(low[root], depth[node]); //邏輯證明 2.2
        else{
            //先進行 DFS，往下找其他的 node 有沒有辦法回到曾經走放過的節點
            find_bridge(node, root); 
            low[root] = min(low[root], low[node]); //邏輯證明 2.3
            if(low[node] > depth[root]){  //邏輯證明 2.4
                int fa_node = find_root(node); //進行 disjoint merge
                int fa_root = find_root(root);
                //cout << "fa " << fa_node << " " << fa_root << "\n";
                ancestor[fa_node] = fa_root;
            }
        }
    }
}

心得

好久沒有學演算法了，真的覺得學演算法是最開心的一件事，總是能透過一些優秀的方式來解決生活上的許多難題，這種動腦的我真的很喜歡。

但是我又感覺我不夠聰明好討厭QQ。

謝謝 cp 用好懂的方式教會我。