In DFS 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 DFS theo thứ tự từ điển (lexicographically) nhỏ nhất bắt đầu từ đỉnh 1. Đỉnh được đánh số từ 1 đến N.

Ví dụ

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

Thay vì DFS thông thường, ta sắp xếp các cạnh kề của mỗi đỉnh theo thứ tự tăng dần, sau đó thực hiện DFS bình thường để được thứ tự từ điển nhỏ nhất.

Thuật toán

BẮT ĐẦU
BƯỚC 1: HÀM lexo(vector* arr, int n)
    bool check[n+1] = {0}
    VỚI i=0 ĐẾN i<n, i++: sort(arr[i].begin(), arr[i].end())
    VỚI i=1 ĐẾN i<n, i++
        NẾU !check[i] THÌ GỌI graph(arr, i, n, check)
BƯỚC 2: HÀM edge(int u, int v, vector* arr)
    arr[u].push_back(v); arr[v].push_back(u)
BƯỚC 3: HÀM graph(vector* arr, int src, int n, bool* check)
    IN src; check[src] = true
    VỚI i=0 ĐẾN i<arr[src].size(), i++
        NẾU !check[arr[src][i]] THÌ GỌI ĐỆ QUY graph(...)
BƯỚC 4: MAIN()
    n=5, m=5; vector arr[n+1]
    GỌI edge(...) cho 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 edge(int u, int v, vector* arr) {
    arr[u].push_back(v);
    arr[v].push_back(u);
}

void graph(vector* arr, int src, int n, bool* check) {
    cout << src << " ";
    check[src] = true;
    for (int i = 0; i < arr[src].size(); i++) {
        if (!check[arr[src][i]])
            graph(arr, arr[src][i], n, check);
    }
}

void lexo(vector* arr, int n) {
    bool check[n+1] = {0};
    for (int i = 0; i < n; i++)
        sort(arr[i].begin(), arr[i].end());
    for (int i = 1; i < n; i++) {
        if (!check[i])
            graph(arr, i, n, check);
    }
}

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); edge(1, 2, arr);
    edge(3, 5, arr); edge(1, 3, arr);
    lexo(arr, n);
    return 0;
}

Kết quả

1 2 3 4 5