二、普里姆算法

　　typedef struct {
　　　VertexType adjvex;
　　　VRType lowcost;
　　}closedge[MAX_VERTEX_NUM];
　　假设cost(u,w)表示边(u,w)上的权值，则对于集合 V-U 中每个顶点 w，
　　　closedge[LocateVex(G, w)].lowcost = Min{cost(u,w)|u∈U}

算法 7.9
　　void MiniSpanTree_PRIM( MGraph G, VertexType u,SqList& MSTree)
　{
　　// G 为数组存储表示的连通网，按普里姆算法从顶点 u 出发构
　　// 造G的最小生成树，顺序表 MSTree 中记录生成树的各条边
　　k = LocateVex ( G, u );
　　InitList(MSTree, G.vexnum); 　　　// 初始化生成树为空树
　　for ( j=0; j<G.vexnum; ++j ) 　　 // 辅助数组初始化
　　　if (j!=k) closedge[j] = { u, G.arcs[k][j].adj };//{adjvex,lowcost}
　　　closedge[k].lowcost = 0; 　　　 // 初始状态，U＝{u}
　　for (i=1; i<G.vexnum; ++i) { 　　// 选择其余 G.vexnum-1 个顶点
　　　k = minimum(closedge);　　　　　// 求出T的下一个结点(图中第k顶点)
　　　// 此时closedge[k].lowcost =
　　　// Min{ closedge[vi].lowcost | closedge[vi].lowcost>0, vi∈V-U }
　　　e.vex1 = closedge[k].adjvex;
　　　e.vex2 = G.vexs[k];
　　　e.weight = closedge[k].lowcost;
　　　b = ListInsert (MSTree, i, e);　// e 为生成树的一条边
　　　closedge[k].lowcost = 0; 　　　// 第 k 顶点并入U集
　　　for (j=0; j<G.vexnum; ++j)
　　　　if (G.arcs[k][j].adj < closedge[j].lowcost)
　　　　　　　　　　　　　　　　　　 // 新顶点并入U后重新选择最小边
  

　普里姆算法构造生成树的过程如动画所示。动画

　

　
　

　

　

　

　
  
  　　　　　closedge[j] = { G.vexs[k], G.arcs[k][j].adj };
　　　} // for
　} // MiniSpanTree		   　　普里姆算法的时间复杂度为O(n2)。可见，普里姆算法适用于稠密图，而克鲁斯卡尔算法适用于稀疏图。