最小全域木
最小全域木
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/03/16 12:19 UTC 版)
各辺に重み（コスト）がある場合、最小の総和コストで構成される全域木を最小全域木という。 クラスカル法 - 単純な貪欲法で計算量は O ( E log E ) {\displaystyle O(E\log {E})} 。 プリム法 - 貪欲法だが計算量は O ( E + V log V ) {\displaystyle O(E+V\log {V})} 。辺の数が頂点に比べて十分大きいときは O ( E ) {\displaystyle O(E)} と見なせる。 辺の重みが均一の場合は幅優先探索で O ( E ) {\displaystyle O(E)} で求まる。
※この「最小全域木」の解説は、「全域木」の解説の一部です。
「最小全域木」を含む「全域木」の記事については、「全域木」の概要を参照ください。
ウィキペディア小見出し辞書の「最小全域木」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ。
- 最小全域木のページへのリンク
