In BFS nhỏ nhất về mặt từ vựng của biểu đồ bắt đầu từ 1 trong Chương trình C.

Chúng ta sẽ được một đồ thị liên thông với N đỉnh M cạnh. Vì vậy, chúng ta phải in BFS nhỏ nhất về mặt từ vựng của biểu đồ bắt đầu từ 1.

Từ vựng có nghĩa là theo thứ tự bắt đầu từ điểm đã cho cho đến khi tìm thấy điểm cuối.

Các ngành dọc phải được đánh số từ 1 đến N

Ví dụ

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

Thay vì thực hiện duyệt BFS thông thường với một hàng đợi đơn giản trên biểu đồ, chúng ta có thể sử dụng một hàng đợi ưu tiên (min heap). Bất cứ khi nào một nút được truy cập, hãy thêm các nút liền kề của nó vào hàng đợi ưu tiên. Mỗi lần, chúng tôi truy cập một nút mới, nó sẽ là nút có chỉ số nhỏ nhất trong hàng đợi ưu tiên. In các nút khi mỗi lần chúng tôi truy cập chúng bắt đầu từ 1.

Thuật toán

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

Ví dụ

#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;
}

Đầu ra

nếu chúng ta chạy chương trình trên thì nó sẽ tạo ra kết quả sau

1 4 3 2 5