BFS vs DFS ビジュアライザー
BFSとDFSが同じグラフをどのように違って探索するかを見てみましょう。BFSは広く、DFSは深く進みます。
Topological Traversal and Complexity Bounds 🖖
Graph traversal algorithms are strictly defined by their data structure dependencies: queues for Breadth-First Search (BFS) and stacks for Depth-First Search (DFS). BFS expands radially, mathematically guaranteeing the shortest unweighted path, whereas DFS probes maximal depth before recursive backtracking. The time complexity for both remains strictly bounded by O(V + E). These deterministic traversal protocols dictate the computational efficiency of network analysis.
同じ地図、異なる旅のしかた 🖖
両者を並べて動かすと気づくことがあります。訪れるノードと辺はまったく同じで、違うのは順序だけです。幅優先探索(BFS)は先へ進む前に現在の近傍をすべて調べるため、境界で待っているすべてのノードを覚えておく必要があります。深さ優先探索(DFS)は一つの枝に踏み込み、いま辿っている経路だけを追います。実用的な結論は、答えが近くにありそうなら BFS、グラフが深くメモリを小さく保ちたいなら DFS を選ぶことです。
どちらの探索も迷路から生まれた 🖖
コンピュータのはるか以前、DFS はフランスの数学者シャルル・ピエール・トレモー(Charles Pierre Trémaux)が1800年代に発表した迷路の歩き方の規則として存在していました。BFS の登場はずっと後で、Edward F. Moore が1959年に The Shortest Path Through a Maze という題名そのままの論文で再発見し、Konrad Zuse も1945年にすでに素描していました。計算機科学の二本の柱は、どちらも元は迷路を抜け出すために考案されたのです。