Prim算法开始随意选择一个结点构成集合V^T，然后不断地在V-V^T中选一条到V^T中某点最短的边，并将其对应的另一个结点加入到V^T中，最终V^T就是最小支撑树。串行算法描述见图6.6.4。注意算法中向量d是最短路向量，对于任何结点v∈(V-V^T)，d[v]存放V^T中各结点到结点v的最小距离。
　　　　　　
　　　　　　　　　　　求最小支撑树的Prim串行算法

　　Prim算法的正确性由如下的定理保证（证明略）：
　　定理6.6.2：设V'是赋权连通图G=(V, E)的结点真子集，e是分跨在V'和V-V'之间的最短边，则G中一定存在包含e的最短树T。

　　由于算法包括两个循环，每个循环都要进行O(n)步，因此整个算法的复杂度是O(n²)。