Kiểm tra đồ thị có hướng có liên thông hay không trong C++

Để kiểm tra tính liên thông của một đồ thị, chúng ta sẽ cố gắng duyệt qua tất cả các nút bằng bất kỳ thuật toán duyệt nào. Sau khi hoàn thành việc duyệt, nếu có bất kỳ nút nào chưa được thăm, thì đồ thị không liên thông.

Đối với đồ thị có hướng, chúng ta sẽ bắt đầu duyệt từ tất cả các nút để kiểm tra tính liên thông. Đôi khi một cạnh chỉ có cạnh ra nhưng không có cạnh vào, nên nút đó sẽ không được thăm từ bất kỳ nút bắt đầu nào khác.

Trong trường hợp này, thuật toán duyệt được sử dụng là DFS đệ quy.

Đầu vào

Ma trận kề của đồ thị:

Đầu ra

Đồ thị là liên thông.

Thuật toán

duyet(u, visited)
Đầu vào: Nút bắt đầu u và mảng visited để đánh dấu nút đã thăm.
Đầu ra: Duyệt tất cả các đỉnh liên thông.
Bắt đầu
    đánh dấu u là đã thăm
    với mọi đỉnh v, nếu v kề với u, thì
        nếu v chưa được thăm, thì
            duyet(v, visited)
        kết thúc nếu
    kết thúc vòng lặp
Kết thúc

laLienThong(dothi)
Đầu vào: Đồ thị.
Đầu ra: True nếu đồ thị liên thông.
Bắt đầu
    định nghĩa mảng visited
    với mọi đỉnh u trong đồ thị, làm
        đặt tất cả các nút là chưa thăm
        duyet(u, visited)
        nếu vẫn còn nút nào chưa thăm, thì
            trả về false
        kết thúc nếu
    kết thúc vòng lặp
    trả về true
Kết thúc

Ví dụ mã C++

#include <iostream>
#define NODE 5
using namespace std;

int graph[NODE][NODE] = {{0, 1, 0, 0, 0},
                         {0, 0, 1, 0, 0},
                         {0, 0, 0, 1, 1},
                         {1, 0, 0, 0, 0},
                         {0, 1, 0, 0, 0}};

void duyet(int u, bool visited[]) {
    visited[u] = true; // đánh dấu v là đã thăm
    for(int v = 0; v < NODE; v++) {
        if(graph[u][v]) {
            if(!visited[v])
                duyet(v, visited);
        }
    }
}

bool laLienThong() {
    bool *vis = new bool[NODE];
    // với mọi đỉnh u làm điểm bắt đầu, kiểm tra xem tất cả các nút có thể nhìn thấy hay không
    for(int u = 0; u < NODE; u++) {
        for(int i = 0; i < NODE; i++)
            vis[i] = false; // khởi tạo như thể không có nút nào được thăm
        duyet(u, vis);
        for(int i = 0; i < NODE; i++) {
            if(!vis[i]) // nếu có nút không được thăm bởi duyệt, đồ thị không liên thông
                return false;
        }
    }
    return true;
}

int main() {
    if(laLienThong())
        cout << "Đồ thị là liên thông.";
    else
        cout << "Đồ thị không liên thông.";
}

Kết quả đầu ra

Đồ thị là liên thông.