Disconnected graph คือกราฟที่มีโหนดอย่างน้อยหนึ่งโหนดที่ไม่ใช่ปลายทางของกราฟ นั่นคือ ไม่ได้เชื่อมต่อ
กราฟที่ไม่เชื่อมต่อ...
ตอนนี้ BFS แบบธรรมดาใช้ได้ก็ต่อเมื่อกราฟเชื่อมต่อกัน คือ โหนดทั้งหมดเข้าถึงได้จากโหนดหนึ่ง ในกราฟที่ไม่เชื่อมต่อข้างต้น เทคนิคนี้ใช้ไม่ได้ เพราะมีโหนดบางส่วนเข้าถึงไม่ได้ โปรแกรมที่ปรับเปลี่ยนต่อไปนี้จึงเหมาะสมกว่าสำหรับการทำ BFS ในกราฟที่ไม่เชื่อมต่อ
ตัวอย่าง
#include<bits/stdc++.h> using namespace std; void insertnode(vector<int> adj[], int u, int v) { adj[u].push_back(v); } void breathFirstSearch(int u, vector<int> adj[], vector<bool> &visited) { list<int> q; visited[u] = true; q.push_back(u); while(!q.empty()) { u = q.front(); cout << u << " "; q.pop_front(); for (int i = 0; i != adj[u].size(); ++i) { if (!visited[adj[u][i]]) { visited[adj[u][i]] = true; q.push_back(adj[u][i]); } } } } void BFSdisc(vector<int> adj[], int V) { vector<bool> visited(V, false); for (int u=0; u<V; u++) if (visited[u] == false) breathFirstSearch(u, adj, visited); } int main() { int V = 5; vector<int> adj[V]; insertnode(adj, 0, 23); insertnode(adj, 0, 4); insertnode(adj, 1, 2); insertnode(adj, 1, 3); insertnode(adj, 1, 4); insertnode(adj, 2, 3); insertnode(adj, 3, 4); BFSdisc(adj, V); return 0; }ผลลัพธ์
0 4 1 2 3
