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

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

그래프에서 간단한 큐로 일반적인 BFS 순회를 수행하는 대신 우선 순위 큐(최소 힙)를 사용할 수 있습니다. 노드를 방문할 때마다 인접 노드를 우선 순위 대기열에 추가합니다. 새로운 노드를 방문할 때마다 우선 순위 대기열에서 인덱스가 가장 작은 노드가 됩니다. 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