FreeStyleWiki

グラフアルゴリズム - 幅優先探索

[アルゴリズム,グラフアルゴリズム]

グラフアルゴリズム - 幅優先探索

  利用例

Wikipedia - 幅優先探索 より

  • グラフ内の全ての連結成分をみつける。幅優先探索で到達するノードの集合は初期ノードを含む最大の連結成分である。
  • 1つの連結成分内の全てのノードをみつける。
  • 辺の重みなしグラフの最小全域木を求める。
  • 辺の重みなしグラフの単一始点最短経路問題を解く。
  • グラフが2部グラフ(Bipartite graph)かどうかテストする。もし幅優先探索の同じ段階のノード集合に存在するノードに合流する辺があるならば、グラフには奇数長の閉路が存在し2部グラフではない。

  出典

  注意

   As pointed above, BFS can only be used to find shortest path in a graph if:
   
   * There are no loops
   * All edges have same weight or no weight.
上で示されるように、幅優先探索は以下の要件を満たすグラフでのみ最短経路を見つけることができる
  • ループがない
  • すべての辺はすべて同じ重みか、重みがない
  • 「辺の重みが全て同一の非負数の場合は幅優先探索が速く、線形時間で最短路を計算可能である。」 Wikipedia - ダイクストラ法
    • つまり辺の重みが1の場合は幅優先探索が使えるが、そうでない場合はダイクストラ法を使うべきである

+ ソースコード(コードが長めなので、短くしたい)