第1题:
连通图的各边权值均不相同,则该图的最小生成树是唯一的。()
第2题:
A.只有一棵
B.有一棵或多棵
C.一定有多棵
D.n+2
第3题:
如下所示是一个带权连通无向图,其最小生成树各边权的总和为
A. 24
B.25
C.26
D.27
第4题:
如下所示是一个带权连通无向图,其最小生成树各边权的总和为
A.24
B.25
C.26
D.27
第5题:
若一个具有n个结点、k条边的非连通无向图是一个森林(n>k),则该森林中必有( )。棵树。
A.k
B.n
C.n-k
D.n+k
第6题:
此题为判断题(对,错)。
第7题:
下列叙述中正确的是( )。A.连通分量是无向图中的极小连通子图 B.生成树是连通图的一个极大连通子图 C.若一个含有n个顶点的有向图是强连通图,则该图中至少有n条弧 D.若一个含有n个顶点的无向图是连通图,则该图中至少有n条边
第8题:
此题为判断题(对,错)。
第9题:
●试题四
阅读下列算法说明和算法,将应填入(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);
}
第10题:
任何一个带权的无向连通图的最小生成树( )
A.只有一棵
B.有一棵或多棵
C.一定有多棵
D.可能不存在