普里姆算法

是图的最小生成树的一种构造算法。

假设 WN=(V,{E}) 是一个含有 n 个顶点的连通网，TV 是 WN 上最小生成树中顶点的集合，TE 是最小生成树中边的集合。显然，在算法执行结束时，TV=V，而 TE 是 E 的一个子集。在算法开始执行时，TE 为空集，TV 中只有一个顶点，因此，按普里姆算法构造最小生成树的过程为：在所有“其一个顶点已经落在生成树上，而另一个顶点尚未落在生成树上”的边中取一条权值为最小的边，逐条加在生成树上，直至生成树中含有 n-1条边为止。

补充：closedge的类型：

struct {

VertexData Adjvex;

int Lowcost;

}closedge[MAX_VERTEX_NUM]; //求最小生成树的辅助数组

void MiniSpanTree_P( MGraph G, VertexType u )

{

//用普里姆算法从顶点u出发构造网G的最小生成树

k = LocateVex ( G, u );

closedge[k].Lowcost = 0; // 初始，U＝{u}

for ( j=0; j<G.vexnum; ++j ) // 辅助数组初始化

if (j!=k)

closedge[j] = { u, G.arcs[k][j] };

for ( i=0; i<G.vexnum; ++i )

{

继续向生成树上添加顶点；

}

k = minimum(closedge);

// 求出加入生成树的下一个顶点(k)

printf(closedge[k].Adjvex, G.vexs[k]);

// 输出生成树上一条边

closedge[k].Lowcost = 0; // 第k顶点并入U集

for (j=0; j<G.vexnum; ++j) //修改其它顶点的最小边

if ( G.arcs[k][j] < closedge[j].Lowcost )

closedge[j] = { G.vexs[k], G.arcs[k][j] };

}