首页 > 试题广场 >

下面是Prim算法的实现,请在括号内将算法补充完整。

[问答题]

下面是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];
                (          );
         }
 }

}

这道题你会答吗?花几分钟告诉大家答案吧!