问答题

阅读下列算法说明和算法，将应填入 (n) 的字句写在答题纸的对应栏内。 【说明】 下列最短路径算法的具体流程如下：首先构造一个只含n个顶点的森林，然后依权值从小到大从连通网中选择不使森林中产生回路的边加入到森林中去，直至该森林变成一棵树为止，这棵树便是连通网的最小生成树。该算法的基本思想是：为使生成树上总的权值之和达 到最小，则应使每一条边上的权值尽可能地小，自然应从权值最小的边选起，直至选出n-1条互不构成回路的权值最小边为止。
【算法】 /*对图定义一种新的表示方法，以一维数组存放图中所有边，并在构建图的存储结构时将它构造为一个“有序表”。以顺序表MSTree返回生成树上各条边。*/ typedef strnct{ VertexType vex 1; VertexType vex2; VRType weight; }EdgeType; typedef ElemType EdgeType; typedefstruct { // 有向网的定义 VertexType vexs[MAX_VERTEX_NUM]; // 顶点信息 EdgeType edge[MAX_EDGE_NUM]; // 边的信息 Mt vexnum,arcnum; // 图中顶点的数目和边的数目 }ELGraph; void MiniSpanTree_Kruskal(ELGraph G, SqList& MSTree){ //G.edge 中依权值从小到大存放有向网中各边 // 生成树的边存放在顺序表 MSTree 中 MFSet F; InitSet(F, G.vexnum); // 将森林 F 初始化为 n 棵树的集合 InitList(MSTree, G.vexaum); // 初始化生成树为空树 i=O; k=l; while( k＜ (1) ) { e = G.edge[i]; // 取第i条权值最小的边 rl = fix_mfset(F, LocateVex(e.vexl)); r2 = (2) // 返回两个顶点所在树的树根 if(ri (3) r2){ // 选定生成树上第k条边 if (Listlnsert(MSTree, k, e)) (4) ; // 插入生成树 mix_mfset(F, ri, r2); // 将两棵树归并为一棵树 } (5) ; //继续考察下一条权值最小边 } Destroy Set(F); }