最小全域木

→クラスカル法

クラスカル法はO(E log E) Eが大きすぎて間に合わない時

• プリム法はフィボナッチヒープと組み合わせればO(E+V log V)
  • 素朴な二分ヒープとの組み合わせでもO((E+V)log V)になる
• Eのソートが線形時間でできればO(E)
  • →線形時間ソート