深さ優先探索（DFS）

イメージ

graph TD
  A((0)) --> B((1))
  A --> C((4))
  B --> D((2))
  B --> E((3))
  C --> F((5))
  C --> G((6))

実装

グラフの隣接リスト表現g上を探索する

dfs.cpp

auto dfs = [&](auto self, int cv) -> void {
    seen[cv] = true;
    
    each(nv, g[cv]) {
        if (seen[nv]) continue;
        self(self, nv);
    }
};

木の場合

木なら1つ前のノードさえ持っていれば良い

dfs.cpp

auto dfs = [&](auto self, int cv, int pv) -> void {
    each(nv, g[cv]) {
        if (nv == pv) continue;
        self(self, nv);
    }
};

バックトラック

一筆書きを探索する場合はseenを戻してやれば良い

dfs.cpp

auto dfs = [&](auto self, int cv) -> void {
    seen[cv] = true;
    
    each(nv, g[cv]) {
        if (seen[nv]) continue;
        self(self, nv);
    }
    seen[cv] = false;
};

ただし、グリッド上でやると $O(4^{HW})$ かかる

参考

• DFS (深さ優先探索) 超入門！ 〜 グラフ・アルゴリズムの世界への入口 〜【前編】 - Qiita
• よくやる再帰関数の書き方 〜 n 重 for 文を機械的に 〜 - けんちょんの競プロ精進記録
• グリッド問題でdfsのバックトラックは指数時間でO(4^HW)がかかってTLEします - Qiita

関連

• 幅優先探索（BFS）
• いもす法