问答题

[说明] 下列最短路径算法的具体流程如下：首先构造一个只含n个顶点的森林，然后依权值从小到大从连通网中选择不使森林中产生回路的边加入到森林中去，直至该森林变成一棵树为止，这棵树便是连通网的最小生成树。该算法的基本思想是：为使生成树上总的权值之和达到最小，则应使每一条边上的权值尽可能地小，自然应从权值最小的边选起，直至选出 n-1条互不构成回路的权值最小边为止。 [算法] /*对图定义一种新的表示方法，以一维数组存放图中所有边，并在构建图的存储结构时将它构造为一个“有序表”。以顺序表MSTree返回生成树上各条边。*/ typedef struct{ VertexType vex1; VertexType vex2;
VRType weight; } EdgeType; typedef ElemType EdgeType; typedef struct { //有向网的定义 VertexType vexs [MAX_VERTEX_N U M ]; //顶点信息 EdgeType edge[ MAX_EDGE_NUM]; //边的信息 int vexnum, arcnum; //图中顶点的数目和边的数目 I 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返回边的顶点所在树的树的根代号，如果边的两个顶点所在树的树根相同，则说明它们已落在同一棵树上。 */ ri = fix_mfset(F, LocateVex(e. vex1) ); r2= (2) ; //返回两个顶点所在树的树根 if(r1 (3) r2) { //选定生成树上第k条边 if(Listlnsert(MSTree,k,e){ (4) ; //插入生成树 mix_mfset( E, r1,r2); //将两棵树归并为一棵树 } (5) ; //继续考察下一条权值最小边 } DestroySet (F); } }