- 現在
- スタック内
- 完了
- 経路
深さ優先探索 (DFS)
深さ優先探索は、片手を壁につけて迷路を歩くようにグラフを探索します。1本の道を行けるところまで進み、新しく行ける場所がなくなったときだけ戻ります。これをスタックで行います。ノードをクリックしてそこから始め、必要ならゴールを選び、探索を1ステップずつ進めて、スタックが伸び縮みする様子、各ノードに付く訪問番号、閉路を作るエッジを見てみましょう。 「再生」で探索を見るか、「ステップ」と「戻る」で1ステップずつ進めます。ステップスライダーをドラッグすると好きな位置に移動できます。ノードをクリックするとスタートになります。クリックを「ゴール」に切り替えて別のノードをクリックすると、そこへの経路を探します。各ノードの数字は訪問した順番で、グラフの下の列はスタックです。スタートから一番上のノードまで並びます。「新しいグラフ」で別のグラフを作ります。ノード数とエッジ数を選べます。ボードを選択した状態では、矢印キーでステップ、スペースキーで再生と一時停止、Home と End で最初と最後に移動します。
使い方
- ノードをクリックしてスタートにします。経路を探すには、クリックを「ゴール」に切り替えて別のノードをクリックします。
- 「再生」を押すか、「ステップ」と「戻る」で1ステップずつ進めます。ステップスライダーをドラッグすると探索の好きな位置に移動できます。
- グラフの下のスタックと各ノードの訪問番号に注目しましょう。「新しいグラフ」で別のグラフを試せます。
深さ優先探索のしくみ
スタートノードをスタックに積みます。あとは繰り返しです。スタックの一番上のノードの、次の隣接ノードを見ます。まだ見ていない隣接ノードには次の訪問番号を付け、到達元のノードを記録して、スタックの一番上に積みます。探索はそこから続きます。一番上のノードに調べる隣接ノードが残っていなければ、そのノードは完了してスタックから降ろされ、探索はその下のノードに戻ります。スタックが空になれば、到達できるノードはすべて訪問済みです。
スタックからわかること
探索は常に一番新しいノードから続くので、スタックは常にスタートから今見ているノードまでの経路です。ゴールに着いたとき、スタックはそこへの経路ですが、たいていは最短ではありません。最短経路は幅優先探索で求まります。向きのないグラフでは、まだスタックにあるノード (直前に来たノードを除く) へのエッジは閉路を作ります。記録したノードは木、つまり深さ優先探索木を作り、ノードが完了する順番はトポロジカルソートの鍵になります。
よくある質問
深さ優先探索とは何ですか?
スタートノードからグラフを探索する方法の一つです。1本の道をできるだけ深く進み、新しく行ける場所がなくなったときだけ戻って別の枝を試します。戻り道を覚えるのにスタックか再帰を使います。
深さ優先探索で最短経路は求まりますか?
いいえ。ゴールへの経路があれば見つけますが、その経路は必要以上にずっと長くなることがあります。DFS は最初に試した枝をとことんたどるからです。エッジの数を最少にしたいなら幅優先探索を、エッジに長さがあるならダイクストラ法を使います。
DFS と BFS の違いは何ですか?
深さ優先探索はスタックを使い、1本の道を深く進んでから戻ります。幅優先探索はキューを使い、輪を描くように均等に広がります。どちらも到達できるノードすべてを、ノード数とエッジ数の和に比例する時間で訪問します。BFS は最短経路を求め、DFS は閉路、迷路、トポロジカルソートに向いています。
DFS はどうやって閉路を見つけますか?
向きのないグラフで、まだスタックにあるノードへのエッジに出会い、そのノードが直前に来たノードでなければ、そのエッジはループを作ります。アプリでは、そのときステータス行に表示されます。
グラフはどこかに送信されますか?
いいえ。グラフの作成と探索はブラウザ内で行われ、最後の設定はこのブラウザのローカルストレージに保存されます。
試してみますか?
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
エディターへ