●试题四 阅读下列算法说明和算法,将应填入(n)的字句写在答题纸的对应栏内。 【说明】 下列最短路

Question

●试题四

阅读下列算法说明和算法，将应填入(n)的字句写在答题纸的对应栏内。

【说明】

下列最短路径算法的具体流程如下：首先构造一个只含n个顶点的森林，然后依权值从小到大从连通网中选择不使森林中产生回路的边加入到森林中去，直至该森林变成一棵树为止，这棵树便是连通网的最小生成树。该算法的基本思想是：为使生成树上总的权值之和达到最小，则应使每一条边上的权值尽可能地小，自然应从权值最小的边选起，直至选出n-1条互不构成回路的权值最小边为止。

图5算法流程图

【算法】

/*对图定义一种新的表示方法，以一维数组存放图中所有边，并在构建图的存储结构时将它构造为一个"有序表"。以顺序表MSTree返回生成树上各条边。*/

typedef struct{

VertexType vex1；

VertexType vex2；

VRType weight；

}EdgeType；

typedef ElemType EdgeType；

typedef struct{//有向网的定义

VertexType vexs[MAX_VERTEX_NUM]；//顶点信息

EdgeType edge[MAX_EDGE_NUM]；//边的信息

int vexnum，arcnum；//图中顶点的数目和边的数目

}ELGraph；

void MiniSpanTree_Kruskal(ELGraph G，SqList& MSTree){

//G.edge 中依权值从小到大存放有向网中各边

//生成树的边存放在顺序表MSTree中

MFSetF；

InitSet(F，G.vexnum)；//将森林F初始化为n棵树的集合

InitList(MSTree，G.vexnum)；//初始化生成树为空树

i=0；k=1；

while(k< (1) ){

e=G.edge[i]；//取第i条权值最小的边

/*函数fix_mfset返回边的顶点所在树的树根代号，如果边的两个顶点所在树的树根相同，则说明它们已落在同一棵树上。*/

rl=fix_mfset(F，LocateVex(e.vex1))；

r2= (2) //返回两个顶点所在树的树根

if(r1 (3) r2){//选定生成树上第k条边

if(ListInsert(MSTree，k，e){ (4) ；//插入生成树

mix_mfset(E，rl，r2)；//将两棵树归并为一棵树

}

(5) ；//继续考察下一条权值最小边

}

DestroySet(F)；

}

Answer 1

正确答案：
●试题四【答案】(1)G.vexnum(2)fix_mfset(F，LocateVex(e.vex2))(3)!=(4)k++(5)i++【解析】本题考查的是克鲁斯卡尔(Kruskal)算法。理解该算法的关键在于：由于生成树上不允许有回路，因此并非每一条居当前权值最小的边都可选。例如，如图2所示的连通网G5，在依次选中了(e，f)，(b，c)，(e，d)和(f，g)的4条边之后，权值最小边为(g，d)，由于g和d已经连通，若加上(g，d)这条边将使生成树上产生回路，显然这条边不可取。同理，边(f，d)也不可取，之后则依次取(a，g)和(a，b)两条边加入到生成树。那么在算法中如何判别当前权值最小边的两个顶点之间是否已经连通?从生成树的构造过程可见，初始态为n个顶点分属n棵树，互不连通，每加入一条边，就将两棵树合并为一棵树，在同一棵树上的两个顶点之间自然相连通。由此判别当前权值最小边是否可取只要判别它的两个顶点是否在同一棵树上即可。