โปรแกรม C++ ตรวจสอบการเชื่อมต่อของ Directed Graph ด้วย BFS

เพื่อตรวจสอบการเชื่อมต่อของกราฟ เราจะพยายามท่องทุกโหนดโดยใช้อัลกอริทึมท่องใดๆ หลังจากท่องเสร็จ หากมีโหนดใดที่ไม่ได้ถูกเยี่ยมชม แสดงว่ากราฟไม่ได้เชื่อมต่อ

สำหรับกราฟมีทิศทาง เราจะเริ่มท่องจากทุกโหนดเพื่อตรวจสอบการเชื่อมต่อ บางครั้งเส้นเชื่อมหนึ่งอาจมีแค่ outward edge แต่ไม่มี inward edge ทำให้โหนดนั้นไม่ถูกเยี่ยมชมจากจุดเริ่มต้นอื่น ในที่นี้ใช้การท่องแบบ BFS แบบ recursive

Input - Adjacency matrix ของกราฟ

Output - The Graph is connected.

อัลกอริทึม

traverse(s, visited)

Input: โหนดเริ่มต้น s และอาร์เรย์ visited

Output: ท่องทุกโหนดที่เชื่อมต่อกัน

Begin
    ทำเครื่องหมาย s ว่า visited
    ใส่ s เข้า queue Q
    จนกว่า Q จะว่าง ทำ
        u = โหนดที่นำออกจาก queue
        สำหรับแต่ละโหนด v ของกราฟ ทำ
            ถ้า u และ v เชื่อมต่อ แล้ว
                ถ้า u ยังไม่ visited แล้ว
                    ทำเครื่องหมาย u ว่า visited
                    ใส่ u เข้า queue Q
                จบ if
            จบ if
        จบ for
    จบ while
End

isConnected(graph)

Input: กราฟ

Output: True ถ้ากราฟเชื่อมต่อ

Begin
    กำหนดอาร์เรย์ visited
    สำหรับทุกโหนด u ในกราฟ ทำ
        ทำเครื่องหมายทุกโหนดว่าไม่ visited
        traverse(u, visited)
        ถ้ามีโหนดที่ยังไม่ visited เหลืออยู่ แล้ว
            return false
        จบ if
    จบ for
    return true
End

ตัวอย่างโค้ด

#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; // ทำเครื่องหมาย v ว่า visited
    queue<int> que;
    que.push(s); // ใส่ s เข้า queue
    
    while(!que.empty()) {
        int u = que.front(); // นำออกจาก queue
        que.pop();
        
        for(int i = 0; i < NODE; i++) {
            if(graph[i][u]) {
                // เมื่อโหนดยังไม่ถูกเยี่ยมชม
                if(!visited[i]) {
                    visited[i] = true;
                    que.push(i);
                }
            }
        }
    }
}

bool isConnected() {
    bool *vis = new bool[NODE];
    // สำหรับทุกโหนด u เป็นจุดเริ่มต้น ตรวจสอบว่าทุกโหนดมองเห็นได้หรือไม่
    for(int u; 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 << "The Graph is connected.";
    else
        cout << "The Graph is not connected.";
}

ผลลัพธ์

The Graph is connected.