Đồ thị liên thông mạnh (Strongly Connected Graphs)

Một đồ thị có hướng được gọi là liên thông mạnh (strongly connected), khi tồn tại đường đi giữa mỗi cặp đỉnh trong một thành phần.

Để giải thuật toán này, đầu tiên dùng thuật toán DFS để lấy thời gian kết thúc của mỗi đỉnh, sau đó tìm thời gian kết thúc của đồ thị chuyển vị (transpose), rồi các đỉnh được sắp xếp theo thứ tự giảm dần bằng sắp xếp topological.

Đầ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 trong đồ thị cho trước:
0 1 2 3 4

Thuật toán

traverse(graph, start, visited)

Đầu vào: Đồ thị sẽ được duyệt, đỉnh bắt đầu, và cờ các nút đã thăm.

Đầu ra: Duyệt qua mỗi nút theo kỹ thuật DFS và hiển thị nút.

Bắt đầu
  đánh dấu start là đã thăm
  với mọi đỉnh v kết nối với start, thực hiện
    nếu v chưa được thăm thì
      traverse(graph, v, visited)
  kết thúc
Kết thúc

topoSort(u, visited, stack)

Đầu vào: Nút bắt đầu, cờ cho các đỉnh đã thăm, ngăn xếp.

Đầu ra: Điền ngăn xếp trong khi sắp xếp đồ thị.

Bắt đầu
  đánh dấu u là đã thăm
  với mọi nút v kết nối với u, thực hiện
    nếu v chưa được thăm thì
      topoSort(v, visited, stack)
  kết thúc
  đẩy u vào ngăn xếp
Kết thúc

getStrongConComponents(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 cả nút chưa thăm
  với mọi đỉnh i trong đồ thị, thực hiện
    nếu i chưa được thăm thì
      topoSort(i, vis, stack)
  kết thúc
  làm cho tất cả nút chưa thăm lại
  transGraph := chuyển vị của đồ thị cho trước
  trong khi stack không rỗng, thực hiện
    lấy nút từ stack gán vào v
    nếu v chưa được thăm thì
      traverse(transGraph, v, visited)
    kết thúc
  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 transGraph[NODE][NODE];

void transpose() {
  // chuyển vị đồ thị và lưu vào transGraph
  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; // đánh dấu v là đã thăm
  cout << u << " ";
  for(int v = 0; v < NODE; v++) {
    if(g[u][v]) {
      if(!visited[v])
        traverse(g, v, visited);
    }
  }
}

void topoSort(int u, bool visited[], stack<int> &stk) {
  visited[u] = true; // đặt nút v là đã thăm
  for(int v = 0; v < NODE; v++) {
    if(graph[u][v]) { // cho tất cả đỉnh v kề với u
      if(!visited[v])
        topoSort(v, visited, stk);
    }
  }
  stk.push(u); // đẩy đỉnh bắt đầu vào stack
}

void getStrongConComponents() {
  stack<int> stk;
  bool vis[NODE];
  for(int i = 0; i < NODE; i++)
    vis[i] = false; // ban đầu tất cả nút chưa thăm
  
  for(int i = 0; i < NODE; i++)
    if(!vis[i]) // khi nút chưa thăm
      topoSort(i, vis, stk);
  
  for(int i = 0; i < NODE; i++)
    vis[i] = false; // làm tất cả nút chưa thăm cho duyệt
  
  transpose(); // tạo đồ thị đảo ngược
  
  while(!stk.empty()) {
    // khi stack chứa phần tử, xử lý theo thứ tự topo
    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();
}

Đầu ra

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