Chương trình C++ kiểm tra tính liên thông của đồ thị có hướng dùng DFS

Để kiểm tra tính liên thông của một đồ thị, chúng ta sẽ cố gắng duyệt 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 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 mà 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 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

traverse(u, visited)

Đầu vào: Đỉnh bắt đầu u và mảng visited để đánh dấu đỉnh đã 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
        Nếu v chưa được thăm
            traverse(v, visited)
Kết thúc

isConnected(graph)

Đầ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ị
        Đặt tất cả nút là chưa thăm
        traverse(u, visited)
        Nếu còn nút nào chưa thăm thì trả về false
    Trả về true
Kết thúc

Mã ví dụ

#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 traverse(int u, bool visited[]) {
    visited[u] = true;
    for(int v = 0; v < NODE; v++) {
        if(graph[u][v]) {
            if(!visited[v])
                traverse(v, visited);
        }
    }
}

bool isConnected() {
    bool *vis = new bool[NODE];
    for(int u = 0; u < NODE; u++) {
        for(int i = 0; i < NODE; i++)
            vis[i] = false;
        traverse(u, vis);
        for(int i = 0; i < NODE; i++) {
            if(!vis[i])
                return false;
        }
    }
    return true;
}

int main() {
    if(isConnected())
        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.