Chương trình C++ kiểm tra đồ thị có hướng yếu liên thông hay mạnh liên thông

Đồ thị có hướng yếu liên thông (weakly connected) hay mạnh liên thông (strongly connected) có thể xác định bằng DFS. Đây là chương trình C++ cho bài toán này.

Các hàm sử dụng

Bắt đầu
  Hàm fillorder() = điền stack với tất cả đỉnh.
    a) Đánh dấu nút hiện tại đã thăm và in ra
    b) Đệ quy cho tất cả đỉnh kề
    c) Tất cả đỉnh đạt được từ v đã xử lý xong, đẩy v vào Stack
Kết thúc

Bắt đầu
  Hàm DFS():
    a) Đánh dấu nút hiện tại đã thăm và in ra
    b) Đệ quy cho tất cả đỉnh kề
Kết thúc

Ví dụ mã nguồn

#include <iostream>
#include <list>
#include <stack>
using namespace std;

class G {
    int m;
    list<int> *adj;
    void fillOrder(int n, bool visited[], stack<int> &Stack);
    void DFS(int n, bool visited[]);
public:
    G(int N);
    void addEd(int v, int w);
    int print();
    G getTranspose();
};

G::G(int m) {
    this->m = m;
    adj = new list<int>[m];
}

void G::DFS(int n, bool visited[]) {
    visited[n] = true;
    cout << n << " ";
    list<int>::iterator i;
    for (i = adj[n].begin(); i != adj[n].end(); ++i)
        if (!visited[*i])
            DFS(*i, visited);
}

G G::getTranspose() {
    G g(m);
    for (int n = 0; n < m; n++) {
        list<int>::iterator i;
        for (i = adj[n].begin(); i != adj[n].end(); ++i)
            g.adj[*i].push_back(n);
    }
    return g;
}

void G::addEd(int v, int w) {
    adj[v].push_back(w);
}

void G::fillOrder(int v, bool visited[], stack<int> &Stack) {
    visited[v] = true;
    list<int>::iterator i;
    for (i = adj[v].begin(); i != adj[v].end(); ++i)
        if (!visited[*i])
            fillOrder(*i, visited, Stack);
    Stack.push(v);
}

int G::print() {
    stack<int> Stack;
    bool *visited = new bool[m];
    for (int i = 0; i < m; i++) visited[i] = false;
    for (int i = 0; i < m; i++)
        if (visited[i] == false)
            fillOrder(i, visited, Stack);
    G graph = getTranspose();
    for (int i = 0; i < m; i++)
        visited[i] = false;
    int count = 0;
    while (Stack.empty() == false) {
        int v = Stack.top();
        Stack.pop();
        if (visited[v] == false) {
            graph.DFS(v, visited);
            cout << endl;
        }
        count++;
    }
    return count;
}

int main() {
    G g(5);
    g.addEd(2, 1);
    g.addEd(3, 2);
    g.addEd(1, 0);
    g.addEd(0, 3);
    g.addEd(3, 1);
    cout << "Các thành phần liên thông mạnh trong đồ thị cho trước:\n";
    if (g.print() > 1) {
        cout << "Đồ thị yếu liên thông (weakly connected).";
    } else {
        cout << "Đồ thị mạnh liên thông (strongly connected).";
    }
    return 0;
}

Kết quả

Các thành phần liên thông mạnh trong đồ thị cho trước:
4
0 1 2 3
Đồ thị yếu liên thông (weakly connected).