最小生成树问题的算法实现及复杂度分析—天津大学计算机科学与技术学院(算法设计与分析

最小生成树问题的算法实现及复杂度分析—天津大学计算机科学与技术学院(算法设计与分析内容摘要：

ocateVex(G,v1)。 j=LocateVex(G,v2)。 if(i0||j0) return ERROR。 G. arcs[i][j].adj=weight。 [j][i].adj=[i][j].adj。 } return OK。 } 3. 最小生成树建立主程序，采用借助辅助数组的方式，对于辅助的数组，以邻接表的选择点加入该数组，然后查找数组中权值最小，且未被选中的顶点，然后返回该边，加入最小生成树中。 void MiniSpanTree_PRIM(MGraph G,VertexType u) { closedge dge。 //申请数组 result pax。 int k,j,i,lax,time = 0,x,y。 lax= 1。 k=LocateVex(G,u)。 // 确 定初 始结 点 的下 标 for(j=0。 j。 ++j) //初始化临时辅助数组 if(j!=k) { dge[j].lowcost=[k][j].adj。 //数组中的 adjvex均为 u，即从 u 开始到所有其他结点的权值赋给了数组中 lowcost dge[j].adjvex=u。 //数组中的下标起箭头的作用，即它是边的第二个尾结点。 } dge[k].lowcost=0。 //u 在数组 dge的下标即为 k，故自身到自身权值标为 0，也表示纳入点集 V。 for(i=1。 i。 ++i) { k=minimun(G,dge)。 // 在 dge数组中找到最小的一条边，并返回尾结点的下标。 coutK 的寻求结果为 (数组 dge 中的下标）： kendl。 coutdge[k].adjvex [k] endl。 //输出边 pax[time].head=dge[k].adjvex。 pax[time].last=[k]。 x=LocateVex(G,dge[k].adjvex)。 y=LocateVex(G,[k])。 pax[time].weight=[x][y].adj。 time++。 dge[k].lowcost=0。 //把下标为 k 的结点纳入点集 V。 标注权值为 0。 for(j=0。 j。 ++j) if([k][j].adjdge[j].lowcost) { //新加入的点到其他各点的权值比原来的权值更小，则 替换。 采取遍历的方法。 dge[j].lowcost=[k][j].adj。 dge[j].adjvex=[k]。 //点的名字进行修改。 } } cout最小生成树为： endl起点 终点 权值endl。 for(time=0。 timelax。 time++) cout pax[time].head pax[time].last pax[time].weightendl。 } 4. 辅助生成。