โปรแกรม C++ ตรวจสอบการเชื่อมต่อของกราฟมีทิศทางด้วย DFS

การตรวจสอบการเชื่อมต่อของกราฟ

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

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

ในกรณีนี้ อัลกอริทึมการท่องคือ DFS แบบเรียกซ้ำ (recursive DFS traversal)

Input: เมทริกซ์ความติดกันของกราฟ

Output: The Graph is connected.

อัลกอริทึม

traverse(u, visited)

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

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

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

isConnected(graph)

Input: กราฟ

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

เริ่มต้น
  ประกาศอาร์เรย์ visited
  สำหรับทุกโหนด u ในกราฟ
    ทำเครื่องหมายทุกโหนดว่าไม่ได้เยี่ยมชม
    traverse(u, visited)
    ถ้ามีโหนดที่ยังไม่ถูกเยี่ยมชมอยู่ ให้คืนค่า false
  คืนค่า true
สิ้นสุด

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

#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 << "The Graph is connected.";
    else
        cout << "The Graph is not connected.";
}

ผลลัพธ์ตัวอย่าง

The Graph is connected.