ডিসকানেক্টেড গ্রাফ হলো এমন গ্রাফ যেখানে এক বা একাধিক নোড গ্রাফের এন্ডপয়েন্ট নয় অর্থাৎ সেগুলো কানেক্টেড নয়।
একটি ডিসকানেক্টেড গ্রাফ...
সিম্পল BFS শুধু তখনই প্রযোজ্য যখন গ্রাফ কানেক্টেড থাকে অর্থাৎ গ্রাফের সব ভার্টেক্স এক নোড থেকে অ্যাক্সেসIBLE থাকে। উপরের ডিসকানেক্টেড গ্রাফে এই টেকনিক কাজ করবে না কারণ কিছু নোড অ্যাক্সেসIBLE নয়। তাই ব্রেডথ ফার্স্ট সার্চ ডিসকানেক্টেড গ্রাফে করার জন্য নিচের মডিফাইড প্রোগ্রামটি ভালো হবে।
উদাহরণ
#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
