Chương trình C++ kiểm tra đồ thị có liên thông mạnh (Strongly Connected)

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

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

Đầu vào: Ma trận kề của đồ thị.

Đầ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ờ visited.

Đầu ra: Duyệt qua từng đỉnh theo kỹ thuật DFS và hiển thị đỉnh.

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

topoSort(u, visited, stack)

Đầu vào — Đỉnh bắt đầu, cờ visited, stack.

Đầu ra — Điền stack khi sắp xếp topo đồ thị.

Bắt đầu
    Đánh dấu u là đã thăm
    Với mọi đỉnh v kề với u
        Nếu v chưa được thăm
            topoSort(v, visited, stack)
    Đẩy u vào stack
Kết thúc

getStrongConComponents(graph)

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

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

Bắt đầu
    Khởi tạo tất cả đỉnh là chưa thăm
    Với mọi đỉnh i trong đồ thị
        Nếu i chưa được thăm
            topoSort(i, vis, stack)
    Đặt lại tất cả đỉnh là chưa thăm
    transGraph := đồ thị chuyển vị của đồ thị cho trước
    Khi stack không rỗng
        Lấy đỉnh từ stack vào v
        Nếu v chưa được thăm
            traverse(transGraph, v, visited)
Kết thúc

Mã ví dụ

#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]) {
            if(!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]) {
            if(!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 << "Các thành phần liên thông mạnh trong đồ thị cho trước: " << endl;
    getStrongConComponents();
}

Kết quả đầu ra

Các thành phần liên thông mạnh trong đồ thị cho trước:
0 1 2 3 4