algorithm - Prim のアルゴリズムと MST

Question

プリムのアルゴリズムの優先キュー実装の最悪のケースの実行が確認されている V 頂点と E エッジを持つグラフのファミリをどのように説明できますか?

Answer 1

まあ、特定の実装がどのように見えるかを正確に知らずに言うのは難しいですが、プリムについて正しく思い出せば、MST を決定する際に常に Θ(E) エッジをチェックする必要があります。プライオリティ キューがバイナリ ヒープとして実装されている場合 (これが標準的な方法です)、各「チェック」は O(log V) であるため、O(E * log V) の最悪の場合の実行時間は常に発生します。