บทนำ
เพื่อตรวจสอบว่ากราฟเชื่อมต่อ (Connected) หรือไม่ จะท่องทุกโหนดด้วยอัลกอริทึมท่องกราฟ หลังท่องเสร็จ หากยังมีโหนดที่ไม่ถูกเยี่ยมชม แสดงว่ากราฟไม่เชื่อมต่อ
สำหรับกราฟมีทิศทาง (Directed Graph) ต้องเริ่มท่องจากทุกโหนด เพราะบางโหนดอาจมี Edge ออกไปอย่างเดียว ไม่มี Edge เข้า ทำให้ไม่ถูกเยี่ยมชมจากจุดเริ่มต้นอื่น
ใช้ Recursive DFS Traversal
อินพุตและเอาต์พุต
Input: เมทริกซ์ติดกัน 5x5 Output: The Graph is connected.
อัลกอริทึม
traverse(u, visited)
Input: โหนดเริ่มต้น u, อาร์เรย์ visited
Output: ท่องโหนดที่เชื่อมต่อทั้งหมด
Begin
mark u visited
for โหนด v ที่ติดกับ u do
if v ไม่ visited then traverse(v, visited)
done
End
isConnected(graph)
Input: กราฟ
Output: True ถ้ากราฟเชื่อมต่อ
Begin
กำหนด visited array
for โหนด u ทุกตัวในกราฟ do
ล้าง visited เป็น unvisited
traverse(u, visited)
if มีโหนด unvisited เหลืออยู่ return false
done
return true
End
ตัวอย่างโค้ด (C++)
#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
ผลลัพธ์
The Graph is connected.
