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 순회를 제공하는 일반 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