问答题
阅读下列算法说明和算法，将应填入 (n) 的字句写在答题纸的对应栏内。
【说明】
下列最短路径算法的具体流程如下：首先构造一个只含n个顶点的森林，然后依权值从小到大从连通网中选择不使森林中产生回路的边加入到森林中去，直至该森林变成一棵树为止，这棵树便是连通网的最小生成树。该算法的基本思想是：为使生成树上总的权值之和达 到最小，则应使每一条边上的权值尽可能地小，自然应从权值最小的边选起，直至选出n-1条互不构成回路的权值最小边为止。
【说明】
下列最短路径算法的具体流程如下：首先构造一个只含n个顶点的森林，然后依权值从小到大从连通网中选择不使森林中产生回路的边加入到森林中去，直至该森林变成一棵树为止，这棵树便是连通网的最小生成树。该算法的基本思想是：为使生成树上总的权值之和达 到最小，则应使每一条边上的权值尽可能地小，自然应从权值最小的边选起，直至选出n-1条互不构成回路的权值最小边为止。
【正确答案】G.vexnum
(2)fix_mfset(F,Locate Vex(e.vex2))
(3) !=
(4)k++
(5)i++
(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棵树，互不连通，每加入一条边，就将两棵树合并为一棵树，在同一棵树上的两个顶点之间自然相连通。由此判别当前权值最小边是否可取只要判别它的两个顶点是否在同一棵树上即可。
本题考查的是克鲁斯卡尔(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棵树，互不连通，每加入一条边，就将两棵树合并为一棵树，在同一棵树上的两个顶点之间自然相连通。由此判别当前权值最小边是否可取只要判别它的两个顶点是否在同一棵树上即可。