→クラスカル法

クラスカル法はO(E log E)

Eが大きすぎて間に合わない時

プリム法はフィボナッチヒープと組み合わせればO(E+V log V)

素朴な二分ヒープとの組み合わせでもO((E+V)log V)になる

Eのソートが線形時間でできればO(E)

→線形時間ソート