আমাদের N শীর্ষবিন্দু M প্রান্ত সহ একটি সংযুক্ত গ্রাফ দেওয়া হবে। তাই আমাদের 1 থেকে শুরু হওয়া গ্রাফের অভিধানিকভাবে ক্ষুদ্রতম BFS প্রিন্ট করতে হবে।
অভিধানের অর্থ হল প্রদত্ত বিন্দু থেকে শুরু করে শেষ বিন্দু পাওয়া পর্যন্ত।
শীর্ষবিন্দুগুলিকে 1 থেকে N
পর্যন্ত নম্বর দেওয়া উচিত৷উদাহরণ
Input: N = 5 M = 5 edges(1,4, arr) edges(3,4, arr) edges(5,4, arr) edges(3,2, arr) edges(1,5, arr) Output: 1 4 3 2 5
গ্রাফে একটি সাধারণ সারি দিয়ে একটি সাধারণ BFS ট্রাভার্সাল করার পরিবর্তে, আমরা একটি অগ্রাধিকার সারি (মিনিট হিপ) ব্যবহার করতে পারি। যখনই একটি নোড পরিদর্শন করা হয় তখনই এর সন্নিহিত নোডগুলিকে অগ্রাধিকার সারিতে যোগ করুন। প্রতিবার, আমরা একটি নতুন নোড পরিদর্শন করি, এটি অগ্রাধিকার সারিতে সবচেয়ে ছোট সূচক সহ একটি হবে। যখনই আমরা 1 থেকে শুরু করে নোডগুলিকে প্রিন্ট করি।
অ্যালগরিদম
Start Step 1 -> Declare Function void lexo(vector<int> array[], int n) Declare bool arr[n + 1] Call memset(arr, 0, sizeof arr) Use STL priority_queue<int, vector<int>, greater<int> > que Set arr[1] = true Call que.push(1) Loop While !que.empty() Declare int now = que.top() Call que.pop() Print now Loop For (auto p : array[now]) IF !arr[p] Call que.push(p) Call arr[p] = true End End End Step 2 -> declare Function void edge(int i, int j, vector<int> ar[]) Call ar[i].push_back(j) Call ar[j].push_back(i) Step 3- > In main() Declare int n = 5, m = 5 Use STL vector<int> arr[n + 1] Call edges(1,4, arr) Call edges(3,4, arr) Call lexo(arr, n) Stop
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
//for finding the graph
void lexo(vector<int> array[], int n){
bool arr[n + 1];
memset(arr, 0, sizeof arr);
priority_queue<int, vector<int>, greater<int> > que;
arr[1] = true;
que.push(1);
while (!que.empty()){
int now = que.top();
que.pop();
cout << now << " ";
for (auto p : array[now]){
if (!arr[p]){
que.push(p);
arr[p] = true;
}
}
}
}
//for generating edge
void edge(int i, int j, vector<int> ar[]){
ar[i].push_back(j);
ar[j].push_back(i);
}
int main(){
int n = 5, m = 5;
vector<int> arr[n + 1];
edges(1,4, arr); //for inserting the edge
edges(3,4, arr);
edges(5,4, arr);
edges(3,2 arr);
edges(1,5, arr);
lexo(arr, n);
return 0;
} আউটপুট
যদি আমরা উপরের প্রোগ্রামটি চালাই তবে এটি নিম্নলিখিত আউটপুট তৈরি করবে
1 4 3 2 5
