場合は全域木と同じであるため明らかに最小全体木問題と等価である。場合は最小経路問題と等価である。困難であるため解くことは容易ではない。閉路にならない最小コストの辺を選んでゆく操作をすべての頂点が接続されるまで繰り返す。この方法で最小全域木となる証明はP.27参照。Algorithm最初に最小コスト2の辺(D,F)をつなげる。次に最小コスト3の辺(B,D),(A,F)のどちらを選んでも良いがここでは(B,D)をつなげる。次の最小コスト3の辺(A,F)をつなげる。次に最小コスト4の辺(A,D),(C,D)だが(A,D)は閉路となるため(C,D)をつなげる。次に最小コスト5の辺(B,C),(C,E)だが(B,C)は閉路となるため(C,E)をつなげる。閉路になるかは接続しようとしている辺の両端が既に選択されているかで判定ができる。全ての頂点と辺が記憶領域に乗る規模の一般的なグラフであれば、最初に全ての辺をソートし重みの低い順に閉路になるかどうかを評価してゆけば良いので実装は容易である。連結部分グラフに対してコストが最小になる方向に拡大してゆく操作を全体が連結グラフとなるまで繰り返すアルゴリズム。最初に任意の頂点を選択し、最もコストの低い辺を選んで接続する。できあがった部分グラフ以外の頂点とを結ぶ最もコストの低い辺を選択する。この操作をすべての頂点が接続するまで繰り返す。選択されている頂点とまだ選択されていない頂点を接続するためプリム法で閉路ができることはない。以下は適当な重み付き隣接行列を定義するとプリム法で最小全域木を作成する。重みの小さい辺を選ぶのに対して、プリム法は選択済みの部分グラフと接続している辺の中から最も重みの小さい辺を選ぶことから、計算量と記憶領域の点で若干優位な実装が可能である。