2. 计算机
  3. 阅读下列算法说明和算法，将应填入(n)的字句写在答题纸的对应栏内。 【说明】 下列最短路径算法的具体流程如下：首先构造一个只含n个顶点的森林，然后依权值从小到大从连通网中选择不使森林中产生回路的边加入到森林中去，直至该森林变成一棵树为止，这棵树

阅读下列算法说明和算法，将应填入(n)的字句写在答题纸的对应栏内。 【说明】 下列最短路径算法的具体流程如下：首先构造一个只含n个顶点的森林，然后依权值从小到大从连通网中选择不使森林中产生回路的边加入到森林中去，直至该森林变成一棵树为止，这棵树

admin2009-02-15  28
问题 阅读下列算法说明和算法，将应填入(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条权值最小的边
              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);
   }
选项
答案(1)G.vexnum (2)fix_mfset(F,Locate Vex(e.vex2)) (3) != (4)k++ (5)i++
解析 本题考查的是克鲁斯卡尔(Kmskal)算法。理解该算法的关键在于：由于生成树上不允许有回路，因此并非每一条居当前权值最小的边都可选。例如，如图7-1所示的连通网G5，在依次选中了(e,f)，(b,c)，(e,d)和(f,g)的4条边之后，权值最小边为(g,d)，由于g和 d已经连通，若加上(g,d)这条边将使生成树上产生回路，显然这条边不可取。同理，边(f,d)也不可取，之后则依次取(a,g)和(a,b)两条边加入到生成树。
   那么在算法中如何判别当前权值最小边的两个顶点之间是否已经连通?从生成树的构造过程可见，初始态为n个顶点分属n棵树，互不连通，每加入一条边，就将两棵树合并为一棵树，在同一棵树上的两个顶点之间自然相连通。由此判别当前权值最小边是否可取只要判别它的两个顶点是否在同一棵树上即可。
转载请注明原文地址:https://kaotiyun.com/show/3wDZ777K
本试题收录于： 软件设计师下午应用技术考试题库软考中级分类
0

软件设计师下午应用技术考试

软考中级

相关试题推荐
随机试题
最新回复(0)