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