พิมพ์ BFS ที่เล็กที่สุดในเชิงศัพท์ของกราฟโดยเริ่มจาก 1 ในโปรแกรม C

เราจะได้กราฟที่เชื่อมต่อกับจุดยอด N จุดยอด M ดังนั้นเราจึงต้องพิมพ์ BFS ที่เล็กที่สุดของกราฟโดยเริ่มจาก 1

Lexicographically หมายถึง เรียงลำดับจากจุดที่กำหนดจนถึงจุดสิ้นสุด

จุดยอดควรมีหมายเลขตั้งแต่ 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