四十三庵

蔀の雑記帳

BFSとDFS

データ構造とアルゴリズム (新・情報 通信システム工学)

Breadth-First Search: 幅優先探索
Depth-First Search: 深さ優先探索

BFSは開始するNodeをキューに入れ、一度デキューしてから、隣接するNodeをキューイングする。
そしてDequeueしたNodeの隣接しているNodeをenqueueする……
(一度enqueueしたNodeはもうenqueueしない)
それをキューが空になるまで繰り返す

DFSは自己の隣接するNodeに対して、再帰関数を使って記述する。
(隣接するNodeがないNodeか訪問済みNodeにたどり着くまで再帰し続ける)