木の走査

根付き木として見る

無向木でも任意の頂点を根に決めれば、親から子へ走査できる。頂点 v の隣接頂点を調べる際、親 p に戻らないことが重要である。

void dfs(int v, int p) {
    for (int to : graph[v]) {
        if (to == p) continue;
        depth[to] = depth[v] + 1;
        dfs(to, v);
    }
}

DFS と BFS

どちらも計算量は $O(V)$。部分木の集約には DFS、根からの距離を層ごとに扱うなら BFS が自然なことが多い。

ダイクストラ法 は、辺重み付きグラフで BFS の考え方を拡張したものとみなせる。