幅優先探索と深さ優先探索

到達可能なノードを訪問する代表的な探索法です。BFSは近いノードから広がり、DFSは一つの経路を深く進んでから戻ります。この実験では探索候補をキューまたはスタックで管理します。

1. 探索法を選び、開始ノードをクリック（現在： A)

2. 探索を実行

未発見発見済み・待機中現在のノード訪問済み探索木の辺

訪問順序

各ステップで探索候補を取り出し、訪問します。訪問済みならスキップします。開始前にノードをクリックすると開始位置を変更できます。

BFSはキュー、DFSはスタック

BFSは新たに発見した隣接ノードをキューの末尾に追加し、先頭から取り出します。距離1のノードを距離2より先に処理するため、重みなしグラフの最短経路に適しています。

DFSは隣接ノードをスタックに積み、最後に追加したノードを先に取り出します。一つの経路を深くたどってから戻るので、迷路、閉路検出、トポロジカルソートなどに使われます。再帰版では呼び出しスタックを利用します。

隣接リストを使う場合、頂点数V、辺数Eに対して、どちらも計算量はO(V + E)です。