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

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

เล็กซิโคกราฟิกหมายถึงลำดับจากจุดเริ่มต้นจนถึงจุดสิ้นสุด

จุดยอดหมายเลข 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 ธรรมดาด้วยคิว ใช้คิวลำดับความสำคัญ (min heap) ทุกครั้งที่เยี่ยมชมโหนด ให้เพิ่มโหนดติดจังเข้าไปในคิว ทุกครั้งที่เยี่ยมชมโหนดใหม่ จะเป็นโหนดที่มีดัชนีน้อยที่สุดในคิว พิมพ์โหนดทุกครั้งที่เยี่ยมชมเริ่มจาก 1

อัลกอริทึม

Start
Step 1 -> Declare Function void lexo(vector array[], int n)
  Declare bool arr[n + 1]
  Call memset(arr, 0, sizeof arr)
  Use STL priority_queue, greater > 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 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 arr[n + 1]
  Call edges(1,4, arr)
  Call edges(3,4, arr)
  Call lexo(arr, n)
Stop

ตัวอย่างโค้ด C++

#include 
using namespace std;
// สำหรับหากราฟ
void lexo(vector array[], int n){
    bool arr[n + 1];
    memset(arr, 0, sizeof arr);
    priority_queue, greater > 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 ar[]){
    ar[i].push_back(j);
    ar[j].push_back(i);
}
int main(){
    int n = 5, m = 5;
    vector arr[n + 1];
    edges(1,4, arr);
    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