下面是Prim算法的实现,请在括号内将算法补充完整。
const int MaxInt =INT-MAX;
const int n=6;//图的顶点数,应由用户定义
typedef int AdjMatrix[n][n];//用二维数组作为邻接矩阵表示
typedef struct { //生成树的边结点
int fromVex, toVex; //边的起点与终点
int weight; //边上的权值
} TreeEdgeNode;
typedef TreeEdgeNode MST[n-1]; //最小生成树定义
void PrimMST( AdjMatrix G, MST T, int rt)}
//从顶点rt出发的构造图G的最小生成树T,rt成为树的根结点
TreeEdgeNode e; int i; k=0, min,minpos ,v;
for (i=0;i<n;i++) //初始化最小生成树T
if(i!=rt)
{
T[k].formVex=rt;
T[k].toVex=i;
T[k++].weight=G[rt][i];
}
for(k=0;k<n-1;k++){ //依次求MST的候选边
min =MaxInt;
for(i=k; i<n-1; i++) //遍历当前候选边集合
if(T[i].weight<min) //选具有最小权值的候选边
{
min =T[i].weight;
( );
}
if(min=MaxInt) //图不连通,出错处理
{
cerr<<”Graph is disconnected!”<<end1;
exit(1);
}
e=T[minpos];
T[minpos]=T[k];
T[k]=e;
v=T[k].toVex;
for(i=k+1;i<n-1;i++) //修改候选边集合
if (G[v][T[i].toVex]<T[i].weight) {
T[i].weight=G[v][T[i].toVex];
( );
}
}
}
