【C++】頂点1から始まるグラフの辞書式最小BFSを出力する方法

問題概要

N個の頂点とM個の辺からなる連結グラフが与えられます。このとき、頂点1から探索を開始した場合の幅優先探索(BFS)の訪問順序のうち、辞書式順序で最小となるものを出力します。

ここで「辞書式順序で最小」とは、各ステップで訪問可能な頂点の中から常に最も小さい番号の頂点を選んでいく順序のことです。

頂点には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では単純なキュー(FIFO)を使用しますが、その場合は隣接頂点のうちどれが先に訪問されるかが辺の登録順に依存してしまいます。そこで、代わりに優先度付きキュー(最小ヒープ)を使用します。

• あるノードを訪問したら、その隣接ノードをすべて優先度付きキューに追加します。
• 次に訪問するノードは、常にキュー内で最も小さい番号を持つノードになります。
• 頂点1から探索を開始し、ノードを訪問するたびに出力していきます。

アルゴリズム

開始
ステップ1 → 関数 void lexo(vector<int> array[], int n) を宣言
    bool arr[n + 1] を宣言
    memset(arr, 0, sizeof arr) を呼び出す
    STL の priority_queue<int, vector<int>, greater<int>> que を用意
    arr[1] = true を設定
    que.push(1) を呼び出す
    !que.empty() の間、以下を繰り返す
        int now = que.top() を宣言
        que.pop() を呼び出す
        now を出力
        (auto p : array[now]) に対してループ
            IF !arr[p] ならば
                que.push(p) を呼び出す
                arr[p] = true を設定
            終了
        終了
    終了
ステップ2 → 関数 void edge(int i, int j, vector<int> ar[]) を宣言
    ar[i].push_back(j) を呼び出す
    ar[j].push_back(i) を呼び出す
ステップ3 → main() 内で
    int n = 5, m = 5 を宣言
    STL の vector<int> arr[n + 1] を用意
    edge(1,4, arr) を呼び出す
    edge(3,4, arr) を呼び出す
    lexo(arr, n) を呼び出す
終了

C++での実装例

#include <bits/stdc++.h>
using namespace std;

// グラフを辞書式順序で探索する関数
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;
            }
        }
    }
}

// 辺を追加する関数
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];
    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;
}

出力結果

上記のプログラムをコンパイルして実行すると、次の出力が得られます。

1 4 3 2 5

動作の流れ

頂点1から開始すると、隣接する頂点は4と5なので、両方が優先度付きキューに追加されます。最小ヒープの性質により、最も小さい「4」が先に取り出され、続いて新たに発見された「3」が追加されて取り出されます。その後「2」が追加され、「2」「5」の順に出力されるため、結果として「1 4 3 2 5」という辞書式最小のBFS順序が得られます。