DFS（深さ優先探索）
グラフ走査アルゴリズム。各枝をできるだけ深く進み、行き止まりで引き返す。再帰またはスタックで実装する。
用途はトポロジカルソート、閉路検出、連結成分の発見、迷路の解法、コンパイラのパスなど。TarjanのSCCや橋検出のアルゴリズムはDFSの上に成り立っている。BFSとの違いは、使うメモリが少ない（深さ d に対し O(d)）が、最短経路は見つからない点だ。スタックによる反復版DFSなら、深いグラフでもスタックオーバーフローを避けられる。git log はコミットのDAGをDFSでたどる。