Time and Space Complexity
Coddyの「プリム法 - グラフアルゴリズム」コースのレッスン 7/9。
時間計算量:
- ここでのエッジスキャン版は O(V * E) です。V-1 回のラウンドがあり、各ラウンドですべての E 個のエッジをスキャンします。バイナリヒープと隣接リストを使用すると、プリム法は O((V + E) log V) で動作します。
空間計算量:
inTree配列（および入力エッジ）に対して O(V) です。
まとめ:
- プリム法は、すべての頂点が含まれるまで、そこから伸びる最も安価なエッジを常に追加しながら、1つの木を成長させます。
- 異なる戦略を使用しますが、クラスカル法と同じ最小合計重みを生成します。
自分で試してみよう
このレッスンにはコードチャレンジは含まれていません。
腕試しこのレッスンには短いクイズがあります。レッスンを始めて解答し、進捗を記録しましょう。
プリム法 - グラフアルゴリズムのすべてのレッスン
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity