全幅探索（読み）ゼンプクタンサク

基本的な概念と定義

• 全幅探索とは、グラフ理論において、与えられた始点から隣接する全ての頂点を訪問し、次にその隣接頂点を訪問するアルゴリズムです。
• 深さ優先探索とは対照的に、全幅探索は幅優先で探索を行うため、最短経路を見つけるのに適しています。
• 全幅探索はキューを用いて実装され、まず始点をキューに追加し、取り出した頂点の隣接頂点を次々とキューに追加する手法です。
• 全幅探索は無向グラフ、有向グラフのどちらにも応用可能で、迷路の最短経路探索などに利用されます。
• 全幅探索の計算量はO(V + E)であり、Vは頂点数、Eは辺の数を表します。

実際の応用例

• 迷路の最短経路を求める際に、全幅探索を使うとどの道が最も効率的かを簡単に見つけることができます。
• ネットワークの障害解析では、全幅探索を用いることで障害部分を迅速に特定することが可能です。
• ソーシャルネットワーク分析では、全幅探索を活用してユーザー間の最短接続経路を明らかにすることができます。
• 全幅探索は、ゲームAIのパスファインディングで広く用いられ、キャラクターの動きを最適化します。
• 検索エンジンのクローリングアルゴリズムにおいても、全幅探索が利用されることがあります。

アルゴリズムの詳細

• 全幅探索ではまず、始点をキューに追加し、訪問済みリストにマークします。
• 全幅探索は、キューの使用によりFIFO（先入れ先出し）を実現し、各頂点を一度だけ訪問します。
• 全幅探索の実装には、キュー、隣接リスト、訪問済みリストの3つのデータ構造が必要です。