プリム法
V は頂点の数、E は辺の数。「重みが最小の辺」をどのように探索するかで計算量が変わる。
グラフを隣接行列で表した単純な実装で、重みの配列を探索して重みが最小の辺を求める場合、 O ( V 2 ) {\displaystyle O(V^{2})} の時間がかかる。単純な二分ヒープと隣接リストを使うと、 O ( ( V + E ) log  V ) {\displaystyle O((V+E)\log V)} の時間がかかる。より洗練されたフィボナッチヒープを使うと、E が Ω ( V log  V ) {\displaystyle \Omega (V\log V)} の程度まで稠密であれば、時間は O ( E + V log  V ) {\displaystyle O(E+V\log V)} とかなり改善される。