トラバーサルを実行する方法
- 01グラフを構築する。プリセットを選んで構築を押します — rows 4、cols 5 のグリッドなら 20 ノードと 31 本の単位辺 — または移動 / 接続で 2 つのノードを順にクリックして辺を描きます。
- 02BFS か DFS を選ぶ。トラバーサルタブで選び、ソースを指定します。構築後はソースがプリセットの最初のノードです。
- 03結果テーブルを読む。BFS は訪問順、最大層、到達不能、木辺を表示し、DFS は前順、後順、後退辺を表示します。キャンバスは訪問済みノードと木辺を着色します。
- 041 ステップずつ進む。再生、前へ / 次へ、スライダーが同じスナップショットをたどるので、授業でキューやスタックの動きが見られます。
ワーク例
以下の数値はすべてパネルからの読み取りです。
| 実行 |
読み取り |
| グリッド 4 × 5、1-1 から BFS |
訪問順 1-1 → 1-2 → 2-1 → 1-3 → 2-2 → 3-1 → … → 4-5、最大層 7、到達不能 —、木辺 19 |
| グリッド 4 × 5、1-1 から DFS |
前順 1-1 → 1-2 → 1-3 → 1-4 → 1-5 → 2-5 → … → 4-1、後順は 4-1 → 4-2 → 4-3 → 4-4 → 4-5 … で始まる、後退辺 31 |
| サイクル C₅、A から BFS |
訪問順 A → B → E → C → D、最大層 2、木辺 4 |
| サイクル C₅、A から DFS |
前順 A → B → C → D → E、後順 E → D → C → B → A |
| 既定のグラフ、A から BFS |
訪問順 A → B → C → D → E → F、最大層 3、木辺 5 |
| 既定のグラフ、A から DFS |
前順 A → B → C → D → E → F、後順 F → E → D → C → B → A、後退辺 9 |
グリッドでは、BFS は 7 ホップで遠い角に到達します — 1-1 と 4-5 のマンハッタン距離です — そしてその 19 本の木辺が 20 ノードの全域木を 1 つ作ります。
同一順序の落とし穴
既定のグラフでは、BFS の訪問順と DFS の前順が同じ文字列 A → B → C → D → E → F を表示するため、順序の行だけではアルゴリズムを特定できません。他の行が特定します。BFS は F を層 3 に置き、DFS は F → E → D → C → B → A で終わり 9 本の後退辺を数えます。無向グラフでは後退辺の行は辺ではなく弧を数えます — グリッドが 31 を報告するのは、31 本の辺が両端から見られるためです(19 本の木弧と 12 本の前向き弧が 62 の残り半分を成します)。最初の行だけでなく表全体を読んでください。
トラバーサルが役立つ場面
まず到達可能性を確認する
BFS はソースが到達できないすべてのノードを列挙します。Random G(n,p) を n 6、p 0.25、seed 20260731 で構築します。キャンバスには成分 A, B, D, E, F と孤立した C が入り、A からの BFS は C を到達不能として名前を挙げます — 成分アルゴリズムが 2 つの成分、最大 5 として報告するのと同じ分割です。
キューとスタックを教える
C₅ で A から両方のアルゴリズムを実行します。BFS は深く進む前に両方の隣接ノードに広がり(A → B → E → C → D)、DFS は 1 つの方向に進み、最後にだけ引き返します(A → B → C → D → E、後順 E → D → C → B → A)。ステップスライダーは、一方ではフロンティアが縮み、他方では広がる様子を示します。
限界
- 重みではなくホップ。
- どちらの走査も辺を数えます。エディターで入力した重みはここでは何も変えません。重み付き経路は最短経路パネルの担当です。
- ソースは 1 つずつ。
- マルチソース BFS はありません。ソースを順に実行してください。パネルはグラフ全体の要約(直径、内周、中心性)やトポロジカル順序付けもしません — それらは指標と中心性と順序と連結性にあります。
- 向きはトグルに従う。
- 有向グラフでは両方の探索が矢印だけをたどります。入ってくる辺で到達するノードは、トグルを戻すまで到達不能のままです。
プライバシー
グラフの編集と両方の探索はブラウザー内で実行されます。何もアップロードされず、最後のグラフはサイトデータを消去するまでローカルストレージに残ります。
参考文献
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022, mitpress.mit.edu (访问日期:2026-10-07)— BFS と DFS、キューとスタックの規律。
- Wikipedia, Breadth-first search, en.wikipedia.org (访问日期:2026-10-07)— 層、距離、木辺。
- Wikipedia, Depth-first search, en.wikipedia.org (访问日期:2026-10-07)— 前順、後順、後退辺。
Calculators in this hub
Hand-picked tools, one click away. The mini versions compute live and carry your values into the full calculator.
Sources & review
- Updated