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

Để 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ị có hướng, chúng ta sẽ bắt đầu duyệt từ tất cả các nút để kiểm tra 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 là BFS đệ quy (recursive BFS 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(s, visited)

Đầu vào: Nút bắt đầu s 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 s đã thăm
    Chèn s vào hàng đợi Q
    Cho đến khi Q không rỗng, thực hiện
        u = nút được lấy ra từ hàng đợi
        Với mỗi nút v của đồ thị, thực hiện
            Nếu u và v kết nối, thì
                Nếu u chưa thăm, thì
                    Đánh dấu u đã thăm
                    Chèn u vào hàng đợi Q.
            Kết thúc
        Kết thúc
    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> 
#include<queue> 
#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 s, bool visited[]) { 
    visited[s] = true; //đánh dấu v đã thăm 
    queue<int> que; 
    que.push(s); //chèn s vào hàng đợi 
    while(!que.empty()) { 
        int u = que.front(); //lấy từ hàng đợi 
        que.pop(); 
        for(int i = 0; i < NODE; i++) { 
            if(graph[i][u]) { 
                //khi nút chưa thăm 
                if(!visited[i]) { 
                    visited[i] = true; 
                    que.push(i); 
                } 
            } 
        } 
    } 
} 

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.