กราฟเชื่อมต่ออย่างแข็งแกร่ง (Strongly Connected Graphs)

กราฟมีทิศทางเรียกว่าเชื่อมต่ออย่างแข็งแกร่ง (Strongly Connected) เมื่อมีเส้นทางระหว่างทุกคู่ของโหนดในคอมโพเนนต์เดียวกัน

วิธีแก้ (Kosaraju's Algorithm):

1. ใช้ DFS หาเวลาสิ้นสุด (Finish Time) ของแต่ละโหนด
2. สร้างกราฟทรานสโพส (Transpose Graph) โดยกลับทิศทางเส้นเชื่อมทั้งหมด
3. เรียงโหนดตามเวลาสิ้นสุดมากไปน้อย (Topological Sort)
4. DFS บนกราฟทรานสโพสตามลำดับนั้น แต่ละครั้งที่ DFS จะได้ 1 SCC

การรับค่าและแสดงผล

Input: เมทริกซ์ตyacency
0 0 1 1 0
1 0 0 0 0
0 1 0 0 0
0 0 0 0 1
0 0 0 0 0

Output: Following are strongly connected components in given graph:
0 1 2 3 4

อัลกอริทึม

traverse(graph, start, visited) - DFS แสดงโหนด

topoSort(u, visited, stack) - Topological Sort

getStrongConComponents(graph) - หา SCC ทั้งหมด

Begin
  ทำเครื่องหมายทุกโหนดว่าไม่ได้เยี่ยมชม
  for ทุกโหนด i do if ไม่ได้เยี่ยมชม then topoSort(i, vis, stack)
  done
  
  ทำเครื่องหมายทุกโหนดว่าไม่ได้เยี่ยมชมอีกครั้ง
  transGraph := transpose ของกราฟเดิม
  
  while stack ไม่ว่าง do
    pop โหนด v จาก stack
    if v ไม่ได้เยี่ยมชม then
      traverse(transGraph, v, visited)
      พิมพ์บรรทัดใหม่ (แยก SCC)
    end if
  done
End

ตัวอย่างโค้ด (C++)

#include <iostream>
#include <stack>
#define NODE 5
using namespace std;

int graph[NODE][NODE] = {
  {0, 0, 1, 1, 0},
  {1, 0, 0, 0, 0},
  {0, 1, 0, 0, 0},
  {0, 0, 0, 0, 1},
  {0, 0, 0, 0, 0}
};

int transGraph[NODE][NODE];

void transpose() {
  for(int i = 0; i < NODE; i++)
    for(int j = 0; j < NODE; j++)
      transGraph[i][j] = graph[j][i];
}

void traverse(int g[NODE][NODE], int u, bool visited[]) {
  visited[u] = true;
  cout << u << " ";
  for(int v = 0; v < NODE; v++)
    if(g[u][v] && !visited[v])
      traverse(g, v, visited);
}

void topoSort(int u, bool visited[], stack<int> &stk) {
  visited[u] = true;
  for(int v = 0; v < NODE; v++)
    if(graph[u][v] && !visited[v])
      topoSort(v, visited, stk);
  stk.push(u);
}

void getStrongConComponents() {
  stack<int> stk;
  bool vis[NODE];
  
  for(int i = 0; i < NODE; i++) vis[i] = false;
  for(int i = 0; i < NODE; i++)
    if(!vis[i]) topoSort(i, vis, stk);
  
  for(int i = 0; i < NODE; i++) vis[i] = false;
  transpose();
  
  while(!stk.empty()) {
    int v = stk.top(); stk.pop();
    if(!vis[v]) {
      traverse(transGraph, v, vis);
      cout << endl;
    }
  }
}

int main() {
  cout << "Following are strongly connected components in given graph: " << endl;
  getStrongConComponents();
}

ผลลัพธ์

Following are strongly connected components in given graph:
0 1 2 3 4