↑: [[G検定に関する知識]] - 一つの分岐を行き止まりまで深く進み、行き止まりになったら戻る（バックトラック） - データ構造：**スタック（Stack / LIFO）**を使用 - メリット：現在の経路情報だけ記憶すればよいためメモリ消費が少ない - デメリット：最初に見つかった経路が最短とは限らない - [[幅優先探索]]と対比で覚える - BFS：最短経路◎、メモリ× - DFS：メモリ◎、最短経路× - 探索木を「一本の枝を選んで行き止まりまで縦に潜る」探索アルゴリズム - 強み：メモリが少なくて済む（今通っている一本道だけ覚えればよい） - cf. [[幅優先探索]]