Chương trình C++ kiểm tra tính liên thông của đồ thị vô 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 sử dụ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ị vô hướng, chúng ta sẽ chọn một nút và duyệt từ nút đó.

Trong trường hợp này, thuật toán duyệt là DFS đệ quy (recursive DFS traversal).

Đầu vào - Ma trận kề của một đồ thị

Đầu ra - Đồ thị là liên thông.

Thuật toán

traverse(u, visited)

Đầu vào - Nút bắt đầu u và mảng visited để đánh dấu nút nào đã thăm.

Đầu ra: Duyệt tất cả các đỉnh kết nối.

Bắt đầu
    Đánh dấu u đã thăm
    Với mọi đỉnh v, nếu v kề với u, thực hiện
        Nếu v chưa thăm, thì
            traverse(v, visited)
    Kết thúc
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ị, thực hiện
        Làm cho tất cả các nút chưa thăm
        traverse(u, visited)
        Nếu vẫn còn nút chưa thăm, thì
            Trả về false
    Kết thúc
    Trả về true
Kết thúc

Mã ví dụ

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

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

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

bool isConnected() { 
    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ả nút có nhìn thấy được không 
    for(int u = 0; u < NODE; u++) { 
        for(int i = 0; i < NODE; i++) 
            vis[i] = false; //khởi tạo chưa nút nào được thăm 
        traverse(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(isConnected()) 
        cout << "Đồ thị là liên thông."; 
    else 
        cout << "Đồ thị không liên thông."; 
}

Kết quả:

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