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

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

สำหรับกราฟไม่มีทิศทาง เราจะเลือกโหนดหนึ่งและท่องจากโหนดนั้น ในที่นี้ใช้การท่องแบบ DFS แบบ recursive

Input - Adjacency matrix ของกราฟ

Output - The Graph is connected.

อัลกอริทึม

traverse(u, visited)

Input: โหนดเริ่มต้น u และอาร์เรย์ visited เพื่อทำเครื่องหมายโหนดที่เยี่ยมชมแล้ว

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

Begin
    ทำเครื่องหมาย u ว่า visited
    สำหรับทุกโหนด v ถ้าติดกับ u ทำ
        ถ้า v ยังไม่ visited แล้ว
            traverse(v, visited)
        จบ if
    จบ for
End

isConnected(graph)

Input: กราฟ

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

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

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

#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; // ทำเครื่องหมาย v ว่า visited
    for(int v = 0; v<NODE; v++) {
        if(graph[u][v]) {
            if(!visited[v])
                traverse(v, visited);
        }
    }
}

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.