อัลกอริทึมของทาร์จัน (Tarjan's Algorithm for SCC)

อัลกอริทึมของทาร์จัน (Tarjan's Algorithm) ใช้หา Strongly Connected Components (SCC) ของกราฟมีทิศทาง ใช้เพียงการ DFS ครั้งเดียว

จาก DFS จะได้ DFS Tree/Forest จากนั้นหา SCC จากรากของแต่ละ subtree เมื่อพบรากของ subtree ที่เป็น SCC จะแสดงโหนดทั้งหมดใน subtree นั้นออกมา

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

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: The strongly connected components: 4 3 1 2 0

อัลกอริทึม

findComponent(u, disc, low, stack, stackItemFlag)

Begin
  time := 0 (static)
  disc[u] := low[u] := ++time
  push u ลง stack, stackItemFlag[u] := true
  
  for ทุกโหนด v ที่ติดกับ u do
    if v ยังไม่ถูกค้นพบ (disc[v] = -1) then
      findComponent(v, disc, low, stack, stackItemFlag)
      low[u] := min(low[u], low[v])
    else if stackItemFlag[v] = true then
      low[u] := min(low[u], disc[v])
    end if
  done
  
  if low[u] = disc[u] then  // u เป็นรากของ SCC
    while top ของ stack != u do
      poppedItem := pop stack
      แสดง poppedItem
      stackItemFlag[poppedItem] := false
    done
    poppedItem := pop stack
    แสดง poppedItem
    stackItemFlag[poppedItem] := false
  end if
End

strongConComponent(graph)

Begin
  ตั้ง disc ทุกตัว = -1, low = φ, stackItemFlag = false
  for ทุกโหนด i do
    if disc[i] = -1 then findComponent(i, disc, low, stack, stackItemFlag)
  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 min(int a, int b) { return (a < b) ? a : b; }

void findComponent(int u, int disc[], int low[], stack<int> &stk, bool stkItem[]) {
  static int time = 0;
  disc[u] = low[u] = ++time;
  stk.push(u);
  stkItem[u] = true;
  
  for(int v = 0; v < NODE; v++) {
    if(graph[u][v]) {
      if(disc[v] == -1) {
        findComponent(v, disc, low, stk, stkItem);
        low[u] = min(low[u], low[v]);
      } else if(stkItem[v]) {
        low[u] = min(low[u], disc[v]);
      }
    }
  }
  
  if(low[u] == disc[u]) {
    while(stk.top() != u) {
      int poppedItem = stk.top();
      cout << poppedItem << " ";
      stkItem[poppedItem] = false;
      stk.pop();
    }
    int poppedItem = stk.top();
    cout << poppedItem << endl;
    stkItem[poppedItem] = false;
    stk.pop();
  }
}

void strongConComponent() {
  int disc[NODE], low[NODE];
  bool stkItem[NODE];
  stack<int> stk;
  
  for(int i = 0; i < NODE; i++) {
    disc[i] = low[i] = -1;
    stkItem[i] = false;
  }
  
  for(int i = 0; i < NODE; i++)
    if(disc[i] == -1)
      findComponent(i, disc, low, stk, stkItem);
}

int main() {
  strongConComponent();
}

ผลลัพธ์

4 3 1 2 0