ブルーフカ法
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2024/05/20 13:54 UTC 版)
その他のアルゴリズムとの比較
クラスカル法はブルーフカ法と同じく、アルゴリズム開始時に全ての頂点でノード一つの木を作成する。それに対して、プリム法では木を最初に決定したひとつの頂点から拡大していく。
知られている最小全域木を求める最適化問題のアルゴリズムの中でもっとも効率の良い バーナード・チャゼル のアルゴリズムは O(E α(E,V)) の計算量で、ブルーフカ法を参考にしている。
関連項目
出典
参考文献
- Nešetřil, Jaroslav, Eva Milková, and Helena Nešetřilová. "Otakar Borůvka on minimum spanning tree problem translation of both the 1926 papers, comments, history." Discrete mathematics 233.1-3 (2001): 3-36. http://www.cs.mun.ca/~kol/courses/6901-f16/boruvka-nmn.pdf
- ^ Borůvka, Otakar (1926). “O jistém problému minimálním [About a certain minimal problem]” (cs, de). Práce Mor. Přírodověd. Spol. V Brně III 3: 37–58 .
- ^ Borůvka, Otakar (1926). “Příspěvek k řešení otázky ekonomické stavby elektrovodních sítí (Contribution to the solution of a problem of economical construction of electrical networks)” (チェコ語). Elektronický Obzor 15: 153–154.
- ^ Nešetřil, Jaroslav; Milková, Eva; Nešetřilová, Helena (2001). “Otakar Borůvka on minimum spanning tree problem: translation of both the 1926 papers, comments, history”. Discrete Mathematics 233 (1–3): 3–36. doi:10.1016/S0012-365X(00)00224-7. hdl:10338.dmlcz/500413. MR1825599.
- ^ Choquet, Gustave (1938). “Étude de certains réseaux de routes” (フランス語). Comptes Rendus de l'Académie des Sciences 206: 310–313.
- ^ Florek, K.; Łukaszewicz, J.; Perkal, J.; Steinhaus, Hugo; Zubrzycki, S. (1951). “Sur la liaison et la division des points d'un ensemble fini” (フランス語). Colloquium Mathematicae 2 (3–4): 282–285. doi:10.4064/cm-2-3-4-282-285. MR0048832 .
- ^ Sollin, Georges (1965). “Le tracé de canalisation” (フランス語). Programming, Games, and Transportation Networks.
- 1 ブルーフカ法とは
- 2 ブルーフカ法の概要
- 3 概要
- 4 その他のアルゴリズムとの比較
- ブルーフカ法のページへのリンク