幅優先探索の応用
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/07/20 15:01 UTC 版)
幅優先探索はグラフ理論における多くの問題を解くために使うことができる。以下は一例である。 グラフ内の全ての連結成分をみつける。幅優先探索で到達するノードの集合は初期ノードを含む最大の連結成分である。 1つの連結成分内の全てのノードをみつける。 辺の重みなしグラフの最小全域木を求める。 辺の重みなしグラフの単一始点最短経路問題を解く。 グラフが2部グラフ(Bipartite graph)かどうかテストする。もし幅優先探索の同じ段階のノード集合に存在するノードに合流する辺があるならば、グラフには奇数長の閉路が存在し2部グラフではない。
※この「幅優先探索の応用」の解説は、「幅優先探索」の解説の一部です。
「幅優先探索の応用」を含む「幅優先探索」の記事については、「幅優先探索」の概要を参照ください。
ウィキペディア小見出し辞書の「幅優先探索の応用」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 幅優先探索の応用のページへのリンク
