【C++】木の部分木のDFS探索順におけるK番目のノードを効率的に求める方法

問題の概要

この記事では、サイズNの木と、木内の頂点V、整数kが与えられたときに、頂点Vを根とする部分木のDFS(深さ優先探索)順においてk番目に訪問されるノードを求める方法を解説します。

つまり、頂点VからDFS探索を開始したときにk番目に現れるノードを求め、そのようなノードが存在しない場合は-1を返します。

入力例

次のような木を考えます(根は頂点5)。

            5
          / | \  \
         8  2  10  3
           / \       \
          6   1       9
                       \
                        7

V = 2、k = 3 の場合:

頂点2を根とする部分木のDFS探索順は {2, 6, 1} となるため、3番目のノードは 1 です。

解法アプローチ

最も単純な解法は、頂点Vから毎回DFSを実行してk番目のノードを直接探すことですが、クエリが多数ある場合には非効率です。

そこでオイラーツアー(Euler Tour)のテクニックを活用します。木全体に対して一度だけDFSを行い、各頂点について「その頂点の部分木のDFS探索の開始位置(startIdx)と終了位置(endIdx)」を記録しておきます。

こうすることで、頂点vの部分木のDFS探索順は、訪問順配列の区間 [startIdx[v], endIdx[v]] に対応します。したがって、k番目のノードは dfsTraversalVector[startIdx[v] + k - 1] を参照するだけでO(1)で求められます。その位置がendIdx[v]を超える場合は、部分木にk個のノードが存在しないため-1を返します。

アルゴリズムの手順

1. 木全体を根からDFSし、訪問順を配列に記録すると同時に、各頂点の開始インデックスと終了インデックスを求める。
2. クエリ(v, k)に対しては、位置 pos = startIdx[v] + k - 1 を計算する。
3. pos ≤ endIdx[v] ならば dfsTraversalVector[pos] を返し、そうでなければ -1 を返す。

C++での実装例

上記の解法を実装したプログラムがこちらです。

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

int n;
vector<int> tree[N];
int currentIdx;
vector<int> startIdx, endIdx;
vector<int> dfsTraversalVector;

void insertEdge(int u, int v){
    tree[u].push_back(v);
    tree[v].push_back(u);
}

void findDfsTraversal(int ch, int par){
    dfsTraversalVector[currentIdx] = ch;
    startIdx[ch] = currentIdx++;
    for (auto c : tree[ch]) {
        if (c != par)
            findDfsTraversal(c, ch);
    }
    endIdx[ch] = currentIdx - 1;
}

int findKNodeDfsV(int v, int k){
    int pos = k + (startIdx[v] - 1);
    if (pos <= endIdx[v])
        return dfsTraversalVector[pos];
    return -1;
}

int main(){
    n = 9;
    insertEdge(5, 8);
    insertEdge(5, 2);
    insertEdge(5, 10);
    insertEdge(5, 3);
    insertEdge(2, 6);
    insertEdge(2, 1);
    insertEdge(3, 9);
    insertEdge(9, 7);

    startIdx.resize(n);
    endIdx.resize(n);
    dfsTraversalVector.resize(n);

    findDfsTraversal(5, 0);

    int v = 2, k = 3;
    cout << "頂点 " << v << " のDFS探索における " << k
         << " 番目のノードは " << findKNodeDfsV(v, k) << endl;
    return 0;
}

出力

頂点 2 のDFS探索における 3 番目のノードは 1

計算量

• 前処理(DFS1回分): O(N)
• 各クエリへの回答: O(1)
• 必要なメモリ: O(N)

まとめ

オイラーツアーを利用することで、木の任意の頂点を根とする部分木のDFS探索順におけるk番目のノードを、前処理O(N)・クエリあたりO(1)という高い効率で求められます。部分木に関するクエリを大量に処理する場面で特に有効なテクニックなので、ぜひマスターしておきましょう。