在一个带权连通图G中，权值最小的边一定包含在G的（）。

B．B．深度优先生成树中

C．C．广度优先生成树中

D．D．深度优先生成森林中

A、某个最小

B、所有最小

C、广度优先

D、深度优先

A、生成树中一定含有权值最小的e条边。

B、生成树中一定可能含有权值最小的n+1条边。

C、生成树中一定含有权值最小的n条边。

D、生成树中一定可能含有权值最小的n-1条边。

A．只要无向连通图中没有权值相同的边，则其最小生成树唯一

B．只要无向图中有权值相同的边，则其最小生成树一定不唯一

C．从n个顶点的连通图中选取n-1条权值最小的边，即可构成最小生成树

D．设连通图G含有n个顶点，则含有n个顶点n-1条边的子图一定是G的生成树

A、图G的一棵最小代价生成树的代价未必小于图G的其他任何一棵生成树的代价

B、一个图的最小生成树可能不唯一，但权值最小的所有边一定会出现在解中

C、若连通图上各边的权值均不相同，则该图的最小生成树是唯一的

D、一个带权的无向连通图的最小生成树的权值之和是唯一的

[说明]

若要在N个城市之间建立通信网络，只需要N-1条线路即可。如何以最低的经济代价建设这个网络，是一个网的最小生成树的问题。现要在8个城市间建立通信网络，其问拓扑结构如图5-1所示，边表示城市间通信线路，边上标示的是建立该线路的代价。

[图5-1]

无向图用邻接矩阵存储，元素的值为对应的权值。考虑到邻接矩阵是对称的且对角线上元素均为0，故压缩存储，只存储上三角元素(不包括对角线)。

现用Prim算法生成网络的最小生成树。由网络G=(V，E)构造最小生成树T=(U，TE)的Prim算法的基本思想是：首先从集合V中任取一顶点放入集合U中，然后把所有一个顶点在集合U里、另一个顶点在集合V-U里的边中，找出权值最小的边(u，v)，将边加入TE，并将顶点v加入集合U，重复上述操作直到U=V为止。

函数中使用的预定义符号如下：

define MAX 32768 /*无穷大权，表示顶点间不连通*/

define MAXVEX 30 /*图中顶点数目的最大值*/

typedef struct{

int startVex，stopVex; /*边的起点和终点*/

float weight; /*边的权*/

}Edge;

typedef struct{

char vexs[MAXVEX]; /*顶点信息*/

float arcs[MAXVEX*(MAXVEX-1)/2]; /*邻接矩阵信息，压缩存储*/

int n; /*图的顶点个数*/

}Graph;

[函数]

void PrimMST(Graph*pGraph, Edge mst[])

{

int i,j,k,min,vx,vy;

float weight，minWeight;

Edge edge;

for(i=0; i＜pGraph-＞n-1；i++){

mst[i].StartVex=0;

mst[i].StopVex=i+1;

mst[i].weight=pGraph-＞arcs[i];

}

for(i=0；i＜(1)；i++){/*共n-1条边*/

minWeight=(float)MAX;

min=i;

/*从所有边(vx，vy)中选出最短的边*/

for(j=i; j＜pGraph-＞n-1; j++){

if(mst[j].weight＜minWeight){

minWeight=(2);

min=j；

}

}

/*mst[minl是最短的边(vx，vy)，将mst[min]加入最小生成树*/

edge=mst[min]；

mst[min]=mst[i];

mst[i]=edge;

vx=(3);/*vx为刚加入最小生成树的顶点下标*/

/*调整mst[i+1]到mst[n-1]*/

for(j=i+1；j＜pGraph-＞n-1；j++){

vy=mst[j].StopVex;

if( (4) ){/*计算(vx，vy)对应的边在压缩矩阵中的下标*/

k=pGraph-＞n*vy-vy*(vy+1)/2+vx-vy-1；

}else{

k=pGraph-＞n*vx-vx*(vx+1)/2+vy-vx-1;

}

weight(5)；

if(weight＜mst[j].weight){

mst[j].weight=weight;

mst[j].StartVex=vx;

}

}

}

}

(1)

[说明]

下列最短路径算法的具体流程如下：首先构造一个只含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); }

}

【说明】 应用Prim算法求解连通网络的最小生成树问题。请阅读程序后填空。

const int MaxInt＝INT MAX； //INT MAX的值在＜limits．h＞中

const int n＝6； //图的顶点数，应由用户定义

typedef int AdjMatrix[n][n]； //用二维数组作为邻接矩阵表示

typedef struct{ //生成树的边结点

int fromVex，to Vex； //边的起点与终点

int weight； //边上的权值

}TreeEdSenode；

typedef TreeEdgeNode MST[n-1]； //最小生成树定义

void PrimMST (AdjMatrix G，MST T，int rt){

//从顶点rt出发构造图G的最小生成树T，rt成为树的根结点

TreeEdgeNode e； int i，k＝0，min，minpos，v；

for(i＝0；i＜n；i++) //初始化最小生成树T

if(i!＝rt){

T[k]．fromVex＝rt；

(1)；

T[k++].weight＝G[rt][i]；

}

for(k＝0；k＜n-1；k++){ //依次求MST的候选边

(2)；

for(i＝k；i＜n-1；i++) 八遍历当前候选边集合

if(T[i].weight＜min) //选具有最小权值的候选边

{min＝T[i]．weight；(3)；}

if(min＝＝MaxInt) //图不连通，出错处理

{cerr＜＜“Graph is disconnected!”＜＜endl； exit(1)；}

e=T[minpos]；T[minpos]＝T[k]；(4)；

v=T[k].to Vex；

for(i＝k+1；i＜n-1；i++) //修改候选边集合

if(G[v][T[i].to Vex]＜T[i].weight){

T[i]．weight＝G[v][T[i].toVex]；

(5)；

}

}

}

B．B 71

C．C 48

D．D 53