在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;
//用于查找图
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;
         }
      }
   }
}
//用于生成边缘
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