C++で解説！頂点1から始まるグラフの辞書式順序で最小のDFSトラバーサルを出力する方法

N個の頂点とM個の辺からなる連結グラフが与えられたとき、頂点1を起点として探索を行う深さ優先探索（DFS）のうち、辞書式順序で最も小さいトラバーサル順を出力することを考えます。

なお、頂点には1からNまでの番号が割り当てられているものとします。

入力例と出力例

Input: N = 5 M = 5
    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)
Output: 1 2 3 4 5

解法のポイント

通常のDFSをそのまま実行した場合、訪問する頂点の順序は隣接リストへの追加順に依存するため、必ずしも辞書式順序で最小になるとは限りません。

そこで本アルゴリズムでは、DFSを開始する前に、各頂点に接続された辺（隣接リスト）をあらかじめ昇順にソートしておきます。これにより、各ステップで常に「最も小さい番号の未訪問頂点」から優先的に訪問できるようになります。ソート後は通常のDFSを実行するだけで、自然と辞書式順序で最小のDFSトラバーサルが得られます。

アルゴリズムの手順

開始
ステップ1 → 関数 lexo(vector<int>* arr, int n) を宣言
    訪問済み判定用の bool 配列 check[n + 1] を { 0 } で初期化
    i = 0 から i < n までループ
        sort(arr[i].begin(), arr[i].end()) を呼び出して隣接リストをソート
    i = 1 から i < n までループ
        もし !check[i] ならば
            graph(arr, i, n, check) を呼び出す
        終了
    終了
ステップ2 → 関数 edge(int u, int v, vector<int>* arr) を宣言
    ar[u].push_back(v) を呼び出す
    ar[v].push_back(u) を呼び出す
ステップ3 → 関数 graph(vector<int>* arr, int src, int n, bool* check) を宣言（src を出力）
    check[src] = true を設定
    i = 0 から i < arr[src].size() までループ
        もし !check[arr[src][i]] ならば
            graph(arr, arr[src][i], n, check) を呼び出す
        終了
    終了
ステップ4 → 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 edge(int u, int v, vector<int>* arr){
    arr[u].push_back(v);
    arr[v].push_back(u);
}
// DFSによるグラフ探索用の関数
void graph(vector<int>* 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);
    }
}
// 辞書式最小のDFSを実現する関数
void lexo(vector<int>* 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<int> 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 関数の呼び出し
    lexo(arr, n);
    return 0;
}

実行結果

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

1 2 3 4 5

計算量について

すべての隣接リストをソートする処理には、全体で O(E log E)（E は辺の総数）の時間がかかります。その後のDFS自体は O(N + E) で完了するため、アルゴリズム全体の計算量は O(E log E) となります。頂点数や辺数が多いグラフでも、この前処理によるソートさえ行えば効率的に辞書式最小のDFS順序を求められるのが大きな特徴です。