訪問済み
スタック内
調べたエッジ

  • 現在
  • スタック内
  • 完了
  • 経路
ノードのクリックで設定

深さ優先探索について詳しく

深さ優先探索 (DFS)

深さ優先探索は、片手を壁につけて迷路を歩くようにグラフを探索します。1本の道を行けるところまで進み、新しく行ける場所がなくなったときだけ戻ります。これをスタックで行います。ノードをクリックしてそこから始め、必要ならゴールを選び、探索を1ステップずつ進めて、スタックが伸び縮みする様子、各ノードに付く訪問番号、閉路を作るエッジを見てみましょう。 「再生」で探索を見るか、「ステップ」と「戻る」で1ステップずつ進めます。ステップスライダーをドラッグすると好きな位置に移動できます。ノードをクリックするとスタートになります。クリックを「ゴール」に切り替えて別のノードをクリックすると、そこへの経路を探します。各ノードの数字は訪問した順番で、グラフの下の列はスタックです。スタートから一番上のノードまで並びます。「新しいグラフ」で別のグラフを作ります。ノード数とエッジ数を選べます。ボードを選択した状態では、矢印キーでステップ、スペースキーで再生と一時停止、Home と End で最初と最後に移動します。

使い方

  1. ノードをクリックしてスタートにします。経路を探すには、クリックを「ゴール」に切り替えて別のノードをクリックします。
  2. 「再生」を押すか、「ステップ」と「戻る」で1ステップずつ進めます。ステップスライダーをドラッグすると探索の好きな位置に移動できます。
  3. グラフの下のスタックと各ノードの訪問番号に注目しましょう。「新しいグラフ」で別のグラフを試せます。

深さ優先探索のしくみ

スタートノードをスタックに積みます。あとは繰り返しです。スタックの一番上のノードの、次の隣接ノードを見ます。まだ見ていない隣接ノードには次の訪問番号を付け、到達元のノードを記録して、スタックの一番上に積みます。探索はそこから続きます。一番上のノードに調べる隣接ノードが残っていなければ、そのノードは完了してスタックから降ろされ、探索はその下のノードに戻ります。スタックが空になれば、到達できるノードはすべて訪問済みです。

スタックからわかること

探索は常に一番新しいノードから続くので、スタックは常にスタートから今見ているノードまでの経路です。ゴールに着いたとき、スタックはそこへの経路ですが、たいていは最短ではありません。最短経路は幅優先探索で求まります。向きのないグラフでは、まだスタックにあるノード (直前に来たノードを除く) へのエッジは閉路を作ります。記録したノードは木、つまり深さ優先探索木を作り、ノードが完了する順番はトポロジカルソートの鍵になります。

よくある質問

深さ優先探索とは何ですか?

スタートノードからグラフを探索する方法の一つです。1本の道をできるだけ深く進み、新しく行ける場所がなくなったときだけ戻って別の枝を試します。戻り道を覚えるのにスタックか再帰を使います。

深さ優先探索で最短経路は求まりますか?

いいえ。ゴールへの経路があれば見つけますが、その経路は必要以上にずっと長くなることがあります。DFS は最初に試した枝をとことんたどるからです。エッジの数を最少にしたいなら幅優先探索を、エッジに長さがあるならダイクストラ法を使います。

DFS と BFS の違いは何ですか?

深さ優先探索はスタックを使い、1本の道を深く進んでから戻ります。幅優先探索はキューを使い、輪を描くように均等に広がります。どちらも到達できるノードすべてを、ノード数とエッジ数の和に比例する時間で訪問します。BFS は最短経路を求め、DFS は閉路、迷路、トポロジカルソートに向いています。

DFS はどうやって閉路を見つけますか?

向きのないグラフで、まだスタックにあるノードへのエッジに出会い、そのノードが直前に来たノードでなければ、そのエッジはループを作ります。アプリでは、そのときステータス行に表示されます。

グラフはどこかに送信されますか?

いいえ。グラフの作成と探索はブラウザ内で行われ、最後の設定はこのブラウザのローカルストレージに保存されます。

試してみますか?

ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。

エディターへ