演算法知識 - Component Kosaraju's Algorithm

Kosaraju’s Algorithm 介紹

Kosaraju’s Algorithm 可以找出有向圖的 SCC

• Sridge-connected Component(強連通分量)
  • Bridge-connected Component 所有兩點之間雙向皆有路可以抵達，圖片由師大演算法提供，不願意讓我放上再請告知我
    

Kosaraju’s Algorithm 原理

證明

• 如果是 A、B、C 三個點都為 SCC，那我從 A 反方向走或正方向走都能走到 A
• 其中圖中有一條邊為 A -> D
  • 如果有一個邊是 D -> A，那我們就可以表示 A、B、C、D 都是 SCC
• 因此我們準備一張反向圖，一樣從 A 出發
  • 題目給的圖如果是 A -> B，則反向圖為 B -> A
• 走訪 A、B、C
  • 同理，如果我能夠滿足此上述條件就表示 A、B、C 為 SCC
• 無法走訪 A、D
• 不可以的話，他們就不是同一組 SCC

原理

• 使用 DFS 實作
• 先進行一次 DFS，並由離開 DFS 的節點順序，依序放入 vector，定義為 path
• 再來根據 path，從最後被加入的節點不斷往前疊代進行 DFS。
  • 這一次 dfs 中，此節點能夠碰到的所有節點都是同一組 scc。

Kosaraju’s Algorithm 實作

不廢話，直接上來

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define MAXN 1020
#define int long long
using namespace std;
vector<int> edge[MAXN]; //題目圖
vector<int> rev_edge[MAXN]; //反向圖
vector<int> path; //紀錄離開 DFS 的節點順序
int visit[MAXN]; 
int group[MAXN]; //判斷此節點在哪一個組
int cnt, a, b, q;

void dfs1(int root){
    if(visit[root]) return;
    visit[root] = 1;

    for(auto it: edge[root]){
        dfs1(it);
    }
    path.push_back(root); //紀錄 DFS 離開的節點
}

void dfs2(int root, int ancestor){
    if(visit[root]) return ;

    visit[root] = 1;
    group[root] = ancestor; //root 跟 ancestor 在同一個 SCC
    for(auto it: rev_edge[root]){
       dfs2(it, ancestor);
    }
}

void kosoraju(){
    for(int i = 0; i < q; i++){ //q 為邊的長度 
        cin >> a >> b;
        edge[a].push_back(b); //題目圖
        rev_edge[b].push_back(a); //反向圖
    }

    memset(visit, 0, sizeof(visit));
    path.clear();
    for(int i = 1; i < cnt; i++){ //第一次 DFS
        if(!visit[i]) dfs1(i);
    }

    memset(visit, 0, sizeof(visit));
    memset(group, 0, sizeof(group));
    for(int i = path.size()-1; i >= 0; i--){ //尋找以 path[i] 為主的 SCC 有哪些節點
        if(!visit[path[i]]){
            dfs2(path[i], path[i]);
        }
    }

}

參考連結

Component: Kosaraju’s Algorithm by 師大演算法

心得

專家們、科學家們研究出來的成果希望我都可以把他們吸收進去，並且運用在我未來的道路上。