Thuật toán Tarjan tìm thành phần liên thông mạnh

Thuật toán Tarjan được dùng để tìm các thành phần liên thông mạnh (Strongly Connected Components - SCC) của một đồ thị có hướng. Nó chỉ yêu cầu một lần duyệt DFS để triển khai thuật toán này.

Sử dụng duyệt DFS ta có thể tìm cây DFS của rừng. Từ cây DFS, các thành phần liên thông mạnh được tìm thấy. Khi tìm thấy gốc của một cây con như vậy, ta có thể hiển thị toàn bộ cây con đó. Cây con đó chính là một thành phần liên thông mạnh.

Đầu vào và Đầu ra

Đầu vào: Ma trận kề của đồ thị.
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
Đầu ra: Các thành phần liên thông mạnh: 4 3 1 2 0

Thuật toán

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

Đầu vào: Nút bắt đầu, thời gian khám phá (discovery time), low, mảng disc giữ thời gian khám phá đỉnh, low giữ thông tin về cây con. Ngăn xếp để giữ đỉnh và mảng cờ khác để theo dõi nút nào trong ngăn xếp.

Đầu ra: Hiển thị SCC.

Bắt đầu
  time := 0 // giá trị time sẽ không khởi tạo lại cho các lần gọi hàm sau
  đặt disc[u] := time+1 và low[u] := time + 1
  time := time + 1
  đẩy u vào stack
  stackItemFalg[u] := true
  với mọi đỉnh v kề với u, thực hiện
    nếu v chưa được khám phá thì
      findComponent(v, disc, low, stack, stackItemFalg)
      low[u] = minimum của low[u] và low[v]
    ngược lại nếu stackItemFalg[v] là true thì
      low[u] := minimum của low[u] và disc[v]
  kết thúc
  poppedItem := 0
  nếu low[u] = disc[u] thì
    trong khi u không ở đỉnh stack, thực hiện
      poppedItem := đỉnh stack
      hiển thị poppedItem
      stackItemFlag[poppedItem] := false
      lấy phần tử ra khỏi stack
    kết thúc
    poppedItem := đỉnh stack
    hiển thị poppedItem
    stackItemFlag[poppedItem] := false
    lấy phần tử ra khỏi stack
  kết thúc nếu
Kết thúc

strongConComponent(graph)

Đầu vào: Đồ thị cho trước.

Đầu ra: Tất cả các thành phần liên thông mạnh.

Bắt đầu
  ban đầu đặt tất cả mục trong mảng disc là chưa khám phá
  với mọi phần tử trong low đặt thành ∅
  và đánh dấu không mục nào lưu trong stack
  với mọi nút i trong đồ thị, thực hiện
    nếu disc[i] chưa khám phá thì
      findComponent(i, disc, low, stack, stackItemFlag)
  kết thúc
Kết thúc

Ví dụ (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; // ban đầu thời gian khám phá và giá trị low là 1
  stk.push(u);
  stkItem[u] = true; // cờ u trong stack
  
  for(int v = 0; v < NODE; v++) {
    if(graph[u][v]) {
      if(disc[v] == -1) { // khi v chưa được thăm
        findComponent(v, disc, low, stk, stkItem);
        low[u] = min(low[u], low[v]);
      } else if(stkItem[v]) // khi v trong stack, cập nhật low cho u
        low[u] = min(low[u], disc[v]);
    }
  }
  
  int poppedItem = 0;
  if(low[u] == disc[u]) {
    while(stk.top() != u) {
      poppedItem = stk.top();
      cout << poppedItem << " ";
      stkItem[poppedItem] = false; // đánh dấu mục đã lấy ra
      stk.pop();
    }
    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++) {
    // khởi tạo tất cả phần tử
    disc[i] = low[i] = -1;
    stkItem[i] = false;
  }
  
  for(int i = 0; i < NODE; i++) // khởi tạo tất cả phần tử
    if(disc[i] == -1)
      findComponent(i, disc, low, stk, stkItem);
}

int main() {
  strongConComponent();
}

Đầu ra

4 3 1 2 0