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は層そうを距離順きょりじゅんに処理しょりするため、無重むおもみグラフの最短距離さいたんきょりを求もとめる。