เพื่อตรวจสอบการเชื่อมต่อของกราฟ เราจะพยายามท่องไปยังโหนดทั้งหมดโดยใช้อัลกอริทึมท่องใดๆ หลังจากท่องเสร็จ หากมีโหนดใดที่ยังไม่ได้ถูกเยี่ยมชม กราฟก็จะไม่ได้เชื่อมต่อ
สำหรับ Directed Graph เราจะเริ่มท่องจากทุกโหนดเพื่อตรวจสอบการเชื่อมต่อ บางครั้งเส้นขอบอาจมีเฉพาะขอบออกไปแต่ไม่มีขอบเข้า ทำให้โหนดนั้นไม่ถูกเยี่ยมชมจากจุดเริ่มต้นอื่น
ในกรณีนี้ อัลกอริทึมท่องที่ใช้คือ DFS แบบเรียกซ้ำ (Recursive DFS Traversal)
อินพุต − เมทริกซ์ตyacency ของกราฟ
| 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 |
เอาต์พุต − กราฟเชื่อมต่อกัน
อัลกอริทึม
traverse(u, visited) Input: โหนดเริ่มต้น u และอาร์เรย์ visited เพื่อทำเครื่องหมายโหนดที่เยี่ยมชมแล้ว Output: ท่องไปยังโหนดที่เชื่อมต่อทั้งหมด Begin mark u as visited for all vertex v, if it is adjacent with u, do if v is not visited, then traverse(v, visited) done End isConnected(graph) Input: กราฟ Output: True หากกราฟเชื่อมต่อ Begin define visited array for all vertices u in the graph, do make all nodes unvisited traverse(u, visited) if any unvisited node is still remaining, then return false done return true End
ตัวอย่าง
#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; // ทำเครื่องหมาย v ว่าเยี่ยมชมแล้ว 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 = 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.
