ধরুন আমাদের একটি অনির্দেশিত গ্রাফ এবং শীর্ষবিন্দুর একটি সেট আছে; প্রদত্ত সেটে উপস্থিত প্রতিটি শীর্ষবিন্দু থেকে আমাদের সমস্ত পৌঁছানো যোগ্য নোডগুলি খুঁজে বের করতে হবে৷
সুতরাং, যদি ইনপুট মত হয়
তাহলে আউটপুট হবে [1,2,3] এবং [4,5] কারণ এই দুটি সংযুক্ত উপাদান।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- নোডস :=গ্রাফে নোডের সংখ্যা
- আকারের পরিদর্শন করা অ্যারে সংজ্ঞায়িত করুন:নোড+1। এবং 0 দিয়ে পূরণ করুন
- একটি মানচিত্র m সংজ্ঞায়িত করুন
- comp_sum :=0
- আরম্ভ করার জন্য i :=0, যখন i
- u :=arr[i]
- যদি পরিদর্শন করা হয়[u] মিথ্যা, তাহলে −
- (1 দ্বারা comp_sum বাড়ান)
- m[visited[u]] :=নোড u থেকে g এর bfs ট্রাভার্সাল, comp_sumও গণনা করুন
- m[দর্শিত[u]] এর প্রিন্ট ট্রাভার্সাল
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
#include <bits/stdc++.h>
using namespace std;
class Graph{
public:
int nodes;
list<int> *adj_list;
Graph(int);
void insert_edge(int, int);
vector<int> BFS(int, int, int []);
};
Graph::Graph(int nodes) {
this->nodes = nodes;
adj_list = new list<int>[nodes+1];
}
void Graph::insert_edge(int u, int v) {
adj_list[u].push_back(v);
adj_list[v].push_back(u);
}
vector<int> Graph::BFS(int comp_sum, int src,int visited[]){
queue<int> queue;
queue.push(src);
visited[src] = comp_sum;
vector<int> reachableNodes;
while(!queue.empty()) {
int u = queue.front();
queue.pop();
reachableNodes.push_back(u);
for (auto itr = adj_list[u].begin(); itr != adj_list[u].end(); itr++) {
if (!visited[*itr]) {
visited[*itr] = comp_sum;
queue.push(*itr);
}
}
}
return reachableNodes;
}
void displayReachableNodes(int n, unordered_map <int, vector<int> > m) {
vector<int> temp = m[n];
for (int i=0; i<temp.size(); i++)
cout << temp[i] << " ";
cout << endl;
}
void get_all_reachable(Graph g, int arr[], int n) {
int nodes = g.nodes;
int visited[nodes+1];
memset(visited, 0, sizeof(visited));
unordered_map <int, vector<int> > m;
int comp_sum = 0;
for (int i = 0 ; i < n ; i++) {
int u = arr[i];
if (!visited[u]) {
comp_sum++;
m[visited[u]] = g.BFS(comp_sum, u, visited);
}
cout << "Reachable Nodes from " << u <<" are\n";
displayReachableNodes(visited[u], m);
}
}
int main() {
int nodes = 5;
Graph g(nodes);
g.insert_edge(1, 2);
g.insert_edge(2, 3);
g.insert_edge(4, 5);
int arr[] = {2, 4, 1};
int n = sizeof(arr)/sizeof(int);
get_all_reachable(g, arr, n);
} ইনপুট
g.insert_edge(1, 2); g.insert_edge(2, 3); g.insert_edge(4, 5);
আউটপুট
Reachable Nodes from 2 are 2 1 3 Reachable Nodes from 4 are 4 5 Reachable Nodes from 1 are 2 1 3
