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