हमें N शीर्षों और M किनारों वाला एक कनेक्टेड ग्राफ़ दिया जाएगा। इसलिए हमें 1 से शुरू होने वाले ग्राफ़ के लेक्सिकोग्राफ़िक रूप से सबसे छोटे DFS को प्रिंट करना होगा।
शीर्षों को 1 से N तक क्रमांकित किया जाना चाहिए
उदाहरण
Input: N = 5 M =5 edge(1, 4, arr) edge(3, 4, arr) edge(5, 4, arr) edge(3, 2, arr) edge(1, 5, arr) edge(1, 2, arr) edge(3, 5, arr) edge(1, 3, arr) output: 1 2 3 4 5
एक सामान्य डीएफएस करने के बजाय, पहले हम प्रत्येक शीर्ष से जुड़े किनारों को क्रमबद्ध करेंगे, ताकि प्रत्येक मोड़ में केवल सबसे छोटा किनारा पहले चुना जाए। छँटाई के बाद, बस एक सामान्य DFS निष्पादित करें जो शब्दावली की दृष्टि से सबसे छोटा DFS ट्रैवर्सल देगा।
नीचे दिए गए एल्गोरिथम का C++ कार्यान्वयन नीचे दिया गया है।
एल्गोरिदम
Start
Step 1 -> Declare Function void lexo(vector<int>* arr, int n)
Declare bool check[n + 1] = { 0 }
Loop For int i=0 and i<n and i++
Call sort(arr[i].begin(), arr[i].end())
Loop For int i = 1 and i < n and i++
IF !check[i]
Call graph(arr, i, n, check)
End
End
Step 2 -> declare Function void edge(int u, int v, vector<int>* arr)
Call ar[u].push_back(v)
Call ar[v].push_back(u)
Step 3 -> Declare function void graph(vector<int>* arr, int src, int n,bool* check) print src
Set check[src] = true
Loop for int i = 0 and i < arr[src].size() and i++
IF !check[arr[src][i]]
Call graph(arr, arr[src][i], n, check)
End
End
Step 4- > 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 inserting an edge
void edge(int u, int v, vector<int>* arr){
arr[u].push_back(v);
arr[v].push_back(u);
}
// Function for dfs graph traversal
void graph(vector<int>* arr, int src, int n,bool* check){
cout << src << " ";
check[src] = true;
for (int i = 0; i < arr[src].size(); i++){
if (!check[arr[src][i]])
graph(arr, arr[src][i], n, check);
}
}
void lexo(vector<int>* arr, int n){
bool check[n + 1] = { 0 };
for (int i = 0; i < n; i++)
sort(arr[i].begin(), arr[i].end());
for (int i = 1; i < n; i++){
if (!check[i])
graph(arr, i, n, check);
}
}
int main(){
int n = 5, m = 5;
vector<int> arr[n + 1];
// for inserting an edge
edge(1, 4, arr);
edge(3, 4, arr);
edge(5, 4, arr);
edge(3, 2, arr);
edge(1, 5, arr);
edge(1, 2, arr);
edge(3, 5, arr);
edge(1, 3, arr);
//call lexo function
lexo(arr, n);
return 0;
} आउटपुट
यदि हम उपरोक्त प्रोग्राम चलाते हैं तो यह निम्न आउटपुट उत्पन्न करेगा
1 2 3 4 5