DFSとBFSの基本きほん

1導入どうにゅう

この講義こうぎでは、深ふかさ優先探索ゆうせんたんさくと幅優先探索はばゆうせんたんさくを候補頂点こうほちょうてんの管理方法かんりほうほうから定義ていぎし、訪問済ほうもんずみ集合しゅうごうが必要ひつような理由りゆう、到達可能性とうたつかのうせいに関かんする正当性せいとうせい、計算量けいさんりょう、BFSが無重むおもみ最短距離さいたんきょりを求もとめる理由りゆうを説明せつめいする。

線形探索せんけいたんさくと二分探索にぶんたんさくは配列はいれつから目標値もくひょうちを探索たんさくした。これに対たいし、この講義こうぎではグラフの頂点ちょうてんを辺へんに沿そって列挙れっきょする探索たんさくを扱あつかう。

グラフの頂点ちょうてん・辺へん・隣接りんせつ・道みち・距離きょりを前提ぜんていとする。未確認みかくにんの場合ばあいは、先さきにグラフの基本きほんを参照さんしょうする。

2共通きょうつうの探索たんさく枠組わくぐみ

グラフ $$G=(V,E)$$G=(V,E) と始点してん $$s\in V$$s\in V を考かんがえる。探索たんさくでは、発見済はっけんずみだが隣接頂点りんせつちょうてんの調査ちょうさを終おえていない頂点ちょうてんを候補こうほとして保持ほじする。

1. 訪問済ほうもんずみ集合しゅうごうを $$S=\left\{s\right\}$$S=\{s\} とし、候補こうほへ $$s$$s を追加ついかする。
2. 候補こうほが空からでない間あいだ、頂点ちょうてん $$v$$v を一ひとつ取とり出だす。
3. $$v$$v の各隣接頂点かくりんせつちょうてん $$u\in N\left(v\right)$$u\in N(v) について、$$u\notin S$$u\notin S なら $$u$$u を $$S$$S と候補こうほへ追加ついかする。

頂点ちょうてんを候補こうほへ追加ついかすると同時どうじに訪問済ほうもんずみにすることが重要じゅうようである。取とり出だした時点じてんまで記録きろくを遅おくらせると、同おなじ頂点ちょうてんが複数ふくすうの辺へんから重複ちょうふくして追加ついかされる。

3DFS

深ふかさ優先探索ゆうせんたんさく（depth-first search; DFS）は候補こうほをスタックで管理かんりし、最後さいごに追加ついかした候補こうほを優先ゆうせんする。再帰版さいきばんでは、ある頂点ちょうてんの未探索みたんさくの隣接頂点りんせつちょうてんを一ひとつ選えらんで再帰呼出さいきよびだしを完了かんりょうしてから次つぎを選えらぶため、一ひとつの道みちを延長えんちょうしてから戻もどる。

再帰さいきによる実装じっそうでは、関数呼出かんすうよびだしのスタックが候補こうほスタックの役割やくわりを担になう。再帰版さいきばんでも、循環じゅんかんを含ふくむグラフで停止ていしするには訪問済ほうもんずみ集合しゅうごうが必要ひつようである。

4BFS

幅優先探索はばゆうせんたんさく（breadth-first search; BFS）は候補こうほをキューで管理かんりする。先さきに追加ついかした頂点ちょうてんを先さきに取とり出だす。

BFSで頂点ちょうてん $$u$$u を初はじめて発見はっけんしたとき、その親おやを $$v$$v として

と記録きろくする。初期値しょきちは $$\ell \left[s\right]=0$$\ell[s]=0 である。まず $$\ell$$\ell を探索たんさくのレベルと呼よび、最短距離さいたんきょりとの一致いっちは次つぎに証明しょうめいする。

5BFS最短性さいたんせいの根拠こんきょ

親おやを順じゅんにたどると、レベル $$\ell \left[u\right]$$\ell[u] の頂点ちょうてん $$u$$u には長ながさ $$\ell \left[u\right]$$\ell[u] の道みちが存在そんざいする。したがって真しんの最短距離さいたんきょりを $$\delta (s,u)$$\delta(s,u) とすれば、$$\delta (s,u)\le \ell \left[u\right]$$\delta(s,u)\leq\ell[u] である。

レベル $$k$$k の頂点ちょうてんから追加ついかされる頂点ちょうてんのレベルは $$k+1$$k+1 であり、それまでにキューへ追加ついかされた頂点ちょうてんより前まえには置おかれない。したがってFIFO順序じゅんじょにより、キューからはレベルの非減少順ひげんしょうじゅんに頂点ちょうてんが取とり出だされる。

逆向ぎゃくむきの不等式ふとうしきを、真しんの距離きょりに関かんする帰納法きのうほうで示しめす。$$\delta (s,u)=0$$\delta(s,u)=0 なら $$u=s$$u=s であり $$\ell \left[u\right]=0$$\ell[u]=0 である。$$\delta (s,u)=r>0$$\delta(s,u)=r>0 とし、最短さいたんの道みちで $$u$$u の直前ちょくぜんにある頂点ちょうてんを $$w$$w とする。$$\delta (s,w)=r-1$$\delta(s,w)=r-1 なので、帰納法きのうほうの仮定かていにより $$\ell \left[w\right]=r-1$$\ell[w]=r-1 である。$$w$$w はレベル $$r$$r の頂点ちょうてんより前まえに処理しょりされ、そのとき $$u$$u が未発見みはっけんなら $$\ell \left[u\right]=r$$\ell[u]=r として発見はっけんされる。すでに発見済はっけんずみなら、そのレベルは $$r$$r 以下いかである。ゆえに $$\ell \left[u\right]\le r=\delta (s,u)$$\ell[u]\leq r=\delta(s,u) である。両方りょうほうの不等式ふとうしきから $$\ell \left[u\right]=\delta (s,u)$$\ell[u]=\delta(s,u) が成立せいりつする。

この主張しゅちょうは各辺かくへんの費用ひようが等ひとしい無重むおもみグラフに限かぎられる。辺へんごとに異ことなる非負ひふの重おもみがある場合ばあいは、Dijkstra法ほうなど別べつの方法ほうほうが必要ひつようである。

6到達可能性とうたつかのうせいと停止性ていしせい

探索中たんさくちゅうに訪問済ほうもんずみとなる頂点ちょうてんは、既知きちの道みちを一辺いっぺんだけ延長えんちょうして発見はっけんされるため、必かならず始点してんから到達可能とうたつかのうである。逆ぎゃくに、長ながさ $$r$$r の道みちで到達とうたつできる頂点ちょうてんが発見はっけんされることを $$r$$r に関かんする帰納法きのうほうで示しめす。$$r=0$$r=0 は始点してんである。$$r>0$$r>0 では、直前ちょくぜんの頂点ちょうてんは帰納法きのうほうの仮定かていにより発見はっけんされ、有限個ゆうげんこの候補こうほが順次処理じゅんじしょりされるため、やがて取とり出だされて次つぎの頂点ちょうてんを発見はっけんする。したがって、DFSとBFSはいずれも到達可能とうたつかのうな頂点ちょうてんをちょうど一度いちどずつ訪問ほうもんする。

有限ゆうげんグラフでは各頂点かくちょうてんを候補こうほへ高々一度たかだかいちどしか追加ついかしないので、探索たんさくは必かならず停止ていしする。

7計算量けいさんりょう

隣接りんせつリストを用もちいる場合ばあい、各頂点かくちょうてんは一度処理いちどしょりされ、無向むこうグラフの各辺かくへんは両端りょうたんから高々一度たかだかいちどずつ調しらべられる。したがってDFSとBFSの時間計算量じかんけいさんりょうは

であり、訪問済ほうもんずみ集合しゅうごうと候補こうほに必要ひつような追加領域ついかりょういきは $$O\left(\right|V\left|\right)$$O(|V|) である。

8使つかい分わけ

• 到達可能性とうたつかのうせいや連結成分れんけつせいぶんの列挙れっきょには、DFSとBFSのどちらも使用しようできる。
• 無重むおもみ最短距離さいたんきょりや最小手数さいしょうてすうにはBFSを使用しようする。
• 再帰的さいきてきな構造こうぞうの調査ちょうさ、帰かえりがけの処理しょり、深ふかい候補こうほの優先ゆうせんにはDFSが適てきする。
• 重おもみ付つき最短距離さいたんきょりにBFSをそのまま使用しようしてはならない。

9まとめ

• DFSとBFSの本質的ほんしつてきな差さは、候補こうほをスタックとキューのどちらで管理かんりするかにある。
• 訪問済ほうもんずみ記録きろくは、循環じゅんかんによる非停止ひていしと候補こうほの重複ちょうふくを防ふせぐ。
• 両者りょうしゃは到達可能とうたつかのうな頂点ちょうてんをちょうど一度いちどずつ訪問ほうもんし、隣接りんせつリストでは $$O\left(\right|V|+|E\left|\right)$$O(|V|+|E|) 時間じかんで動作どうさする。
• BFSは層そうを距離順きょりじゅんに処理しょりするため、無重むおもみグラフの最短距離さいたんきょりを求もとめる。

DFS and BFS Basics

1Introduction

This lecture defines depth-first search and breadth-first search through their management of candidate vertices and explains why a visited set is necessary, why both traversals correctly characterize reachability, their complexity, and why BFS computes unweighted shortest-path distances.

Linear search and binary search locate a target value in an array. This lecture instead considers traversals that enumerate graph vertices by following edges.

The lecture assumes the definitions of vertices, edges, adjacency, paths, and distance. Review Graph Basics first if these concepts are unfamiliar.

2A common traversal framework

Let $$G=(V,E)$$G=(V,E) be a graph with a starting vertex $$s\in V$$s\in V. A traversal stores discovered vertices whose neighbors have not yet been fully examined as candidates.

1. Initialize the visited set as $$S=\left\{s\right\}$$S=\{s\} and add $$s$$s to the candidates.
2. While candidates remain, remove one vertex $$v$$v.
3. For each neighbor $$u\in N\left(v\right)$$u\in N(v), if $$u\notin S$$u\notin S, add $$u$$u to both $$S$$S and the candidates.

A vertex must be marked visited when it is added. If marking is delayed until removal, multiple edges may add the same vertex repeatedly.

3DFS

Depth-first search (DFS) manages candidates with a stack and prioritizes the most recently added candidate. In a recursive implementation, DFS chooses one unexamined neighbor and completes that recursive call before examining the next neighbor. It therefore extends one path and then backtracks.

In a recursive implementation, the function-call stack acts as the candidate stack. Even in the recursive version, a visited set is required for termination on graphs containing cycles.

4BFS

Breadth-first search (BFS) manages candidates with a queue. When BFS first discovers a vertex $$u$$u from its parent $$v$$v, it records the traversal level

with $$\ell \left[s\right]=0$$\ell[s]=0. The next section proves that this level equals the shortest-path distance in an unweighted graph.

5Why BFS gives shortest distances

Let $$\delta (s,u)$$\delta(s,u) denote the true shortest-path distance. The parent chain by which BFS discovers $$u$$u is a path of length $$\ell \left[u\right]$$\ell[u], so $$\delta (s,u)\le \ell \left[u\right]$$\delta(s,u)\leq \ell[u].

A vertex added from a level-$$k$$k vertex has level $$k+1$$k+1 and is placed after vertices already in the queue. FIFO order therefore makes queue removals occur in nondecreasing level order. We prove the reverse inequality by induction on $$r=\delta (s,u)$$r=\delta(s,u). The case $$r=0$$r=0 is the start vertex. For $$r>0$$r>0, let $$w$$w be the predecessor of $$u$$u on a shortest path. By the induction hypothesis, $$\ell \left[w\right]=r-1$$\ell[w]=r-1. When $$w$$w is processed, either it discovers $$u$$u at level $$r$$r or $$u$$u has already been discovered at a level at most $$r$$r. Hence $$\ell \left[u\right]\le \delta (s,u)$$\ell[u]\leq\delta(s,u), and the two inequalities give $$\ell \left[u\right]=\delta (s,u)$$\ell[u]=\delta(s,u).

This claim is restricted to unweighted graphs, where every edge has equal cost. Graphs with unequal nonnegative edge weights require another method, such as Dijkstra's algorithm.

6Reachability and termination

Every visited vertex is reached by extending a known path by one edge, so it is reachable from the start. Conversely, use induction on the length $$r$$r of a path from the start. The case $$r=0$$r=0 is the start vertex. For $$r>0$$r>0, the preceding vertex is discovered by the induction hypothesis. Because the finite candidate set is processed in turn, that vertex is eventually removed and discovers the next vertex. Hence both DFS and BFS visit every reachable vertex exactly once.

In a finite graph, each vertex is added to the candidates at most once, so the traversal terminates.

7Complexity

With adjacency lists, each vertex is processed once, and each undirected edge is examined at most once from each endpoint. Therefore both DFS and BFS take

time and require $$O\left(\right|V\left|\right)$$O(|V|) additional space for the visited set and candidates.

8Choosing between them

• Either DFS or BFS can enumerate reachable vertices and connected components.
• Use BFS for unweighted shortest distances and minimum-step problems.
• DFS is suitable for recursive structure, postorder processing, and prioritizing deeper candidates.
• Do not apply ordinary BFS to shortest paths with unequal edge weights.

9Summary

• The essential difference between DFS and BFS is whether candidates are managed by a stack or a queue.
• The visited set prevents nontermination on cycles and duplicate candidates.
• Both traversals visit each reachable vertex exactly once and run in $$O\left(\right|V|+|E\left|\right)$$O(|V|+|E|) time with adjacency lists.
• BFS processes layers in distance order and therefore computes shortest distances in unweighted graphs.