NISHIO Hirokazu[Translate]
最小全域木

クラスカル法はO(E log E)
Eが大きすぎて間に合わない時
プリム法フィボナッチヒープと組み合わせればO(E+V log V)
素朴な二分ヒープとの組み合わせでもO((E+V)log V)になる
Eのソートが線形時間でできればO(E)


"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]

(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]