समस्या विवरण
हमें N शीर्ष और M किनारों वाला एक जुड़ा हुआ ग्राफ दिया जाएगा। हमें 1 से शुरू होने वाले ग्राफ का लेक्सिकोग्राफिकली सबसे छोटा DFS प्रिंट करना है।
शीर्षों को 1 से N तक नंबर दिया जाना चाहिए।
उदाहरण
इनपुट: N = 5, M = 5 किनारे: (1,4), (3,4), (5,4), (3,2), (1,5), (1,2), (3,5), (1,3) आउटपुट: 1 2 3 4 5
सामान्य DFS करने के बजाय, पहले हम प्रत्येक शीर्ष से जुड़े किनारों को सॉर्ट करेंगे, ताकि प्रत्येक चरण में सबसे छोटा किनारा पहले चुना जाए। सॉर्ट करने के बाद, सामान्य DFS करने से लेक्सिकोग्राफिकली सबसे छोटा DFS ट्रैवर्सल मिलेगा।
एल्गोरिदम
शुरुआत चरण 1: void lexo(vector* arr, int n) फंक्शन घोषित करें bool check[n + 1] = { 0 } घोषित करें i = 0 से n-1 तक लूप sort(arr[i].begin(), arr[i].end()) कॉल करें i = 1 से n-1 तक लूप यदि !check[i] तो graph(arr, i, n, check) कॉल करें अंत अंत चरण 2: void edge(int u, int v, vector * arr) फंक्शन घोषित करें ar[u].push_back(v) कॉल करें ar[v].push_back(u) कॉल करें चरण 3: void graph(vector * arr, int src, int n, bool* check) फंक्शन घोषित करें src प्रिंट करें check[src] = true सेट करें i = 0 से arr[src].size()-1 तक लूप यदि !check[arr[src][i]] तो graph(arr, arr[src][i], n, check) कॉल करें अंत अंत चरण 4: main() में n = 5, m = 5 घोषित करें STL vector arr[n + 1] उपयोग करें edges(1,4, arr) कॉल करें edges(3,4, arr) कॉल करें... lexo(arr, n) कॉल करें रोकें
C++ प्रोग्राम उदाहरण
#include <bits/stdc++.h> using namespace std; // किनारा डालने के लिए void edge(int u, int v, vector* arr){ arr[u].push_back(v); arr[v].push_back(u); } // DFS ग्राफ ट्रैवर्सल के लिए फंक्शन void graph(vector * 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 * 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 arr[n + 1]; 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); lexo(arr, n); return 0; }
आउटपुट
उपरोक्त प्रोग्राम चलाने पर निम्नलिखित आउटपुट उत्पन्न होगा:
1 2 3 4 5
