In BFS theo thứ tự từ điển nhỏ nhất từ đỉnh 1 trong C

Cho đồ thị liên thông N đỉnh, M cạnh. In ra BFS theo thứ tự từ điển nhỏ nhất bắt đầu từ đỉnh 1.

Thay vì dùng hàng đợi thường, ta dùng hàng đợi ưu tiên (min-heap). Mỗi khi thăm đỉnh, thêm các đỉnh kề vào heap. Luôn lấy đỉnh có chỉ số nhỏ nhất từ heap.

Ví dụ

Input: N=5, M=5
Edges: (1,4), (3,4), (5,4), (3,2), (1,5)
Output: 1 4 3 2 5

Thuật toán

BẮT ĐẦU
BƯỚC 1: HÀM lexo(vector array[], int n)
    bool arr[n+1]; memset(arr, 0, sizeof arr)
    priority_queue, greater> que
    arr[1] = true; que.push(1)
    KHI !que.empty() LẶP
        now = que.top(); que.pop()
        IN now
        VỚI p IN array[now]
            NẾU !arr[p] THÌ que.push(p), arr[p] = true
    KẾT THÚC KHI
BƯỚC 2: HÀM edge(int i, int j, vector ar[])
    ar[i].push_back(j); ar[j].push_back(i)
BƯỚC 3: MAIN()
    n=5, m=5; vector arr[n+1]
    GỌI edge(...) các cặp
    GỌI lexo(arr, n)
KẾT THÚC

Chương trình C++ ví dụ

#include <bits/stdc++.h>
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];
    edge(1, 4, arr); edge(3, 4, arr); edge(5, 4, arr);
    edge(3, 2, arr); edge(1, 5, arr);
    lexo(arr, n);
    return 0;
}

Kết quả

1 4 3 2 5