हमें 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
ग्राफ पर एक साधारण कतार के साथ सामान्य बीएफएस ट्रैवर्सल करने के बजाय, हम प्राथमिकता कतार (न्यूनतम ढेर) का उपयोग कर सकते हैं। जब भी किसी नोड का दौरा किया जाता है तो उसके आसन्न नोड्स को प्राथमिकता कतार में जोड़ें। हर बार, हम एक नए नोड पर जाते हैं, यह प्राथमिकता कतार में सबसे छोटा सूचकांक होगा। हर बार जब हम 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