C 프로그램에서 1부터 시작하여 사전순으로 가장 작은 그래프의 DFS를 인쇄합니다.

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