如图4-41所示为一个5个顶点的带权无向图 从顶点a出发，画出相应的广度优先搜索生成树和深度优先搜索生成树（当从某个顶点出发搜索它的邻接点时，请按邻接点序号递增序搜索） 从顶点a出发，画出按照普里姆算法构造的最小生成树，并给出构造过程中的加边顺序

有一个用于n个顶点连通带权无向图的算法描述如下：(1)设集合T1与T2，初始均为空；(2)在连通图上任选一顶点加入T1；(3)以下步骤重复n一1次：A.在i属于T1，j不属于T1的边中选最小权的边；B.该边加入T2。上述算法完成后，T2中共有①条边，该算法称②算法，T2中的边构成图的③。【南京理工大学1999二、7(4分)】

在具有6个顶点的无向简单图中，当边数最少为(26)条时，才能确保该图一定是连通图，当边数最少为(27)条时，才能确保该图一定是哈密尔顿图。

给定带权的有向图，如下图所示。设该图代表一个地区的交通图，从S到T的最短路径有(28)条，路径的长度是(29)，从S出发经过每点一次且只有一次到T的路径(哈密尔顿路径)有(30)条。

A．11

B．12

C．13

D．55

已知顶点1～6和输入边与权值的序列(如右图所示)：每行三个数表示一条边的两个端点和其权值，共11行。请你：

(1)采用邻接多重表表示该无向网，用类Pascal语言描述该数据结构，画出存储结构示意图，要求符合在边结点链表头部插入的算法和输入序列的次序。 (2)分别写出从顶点1出发的深度优先和广度优先遍历顶点序列，以及相应的生成树。 (3)按Prim算法列表计算，从顶点1始求最小生成树，并图示该树。【北京工业大学1999四(20分)】

问题描述:给定一个赋权无向图G=(V,E),每个顶点都有权值w(v).如果,且对任意(u,V)∈E有u∈U或v∈U,就称U为图G的一个顶点覆盖.G的最小权顶点覆盖是指G中所含顶点权之和最小的顶点覆盖.

算法设计:对于给定的无向图G,设计一个优先队列式分支限界法,计算G的最小权顶点覆盖.

数据输入:由文件input.txt给出输入数据.第1行有2个正整数n和m,表示给定的图G有n个顶点和m条边,顶点编号为1,2,...,n.第2行有n个正整数表示n个顶点的权.接下来的m行中,每行有2个正整数u和v,表示图G的一条边(u,v).

结果输出:将计算的最小权顶点覆盖的顶点权值和以及最优解输出到文件output.txt.文件的第1行是最小权顶点覆盖顶点权之和;第2行是最优解xi(1≤i≤n),xi=0表示顶点i不在最小权顶点覆盖中,xi=1表示顶点i在最小权顶点覆盖中.

阅读下列函数说明和C代码，将应填入(n)处的字句写上。

[说明]

若要在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)

已知一个无向图(边为正数)中顶点A,B的一条最短路P，如果把各个边的权重(即相邻两个顶点的距离)变为原来的2倍，那么在新图中，P仍然是A,B之间的最短路，以上说法是()

A.错误

B.正确

A、1句

B、2句

C、3句

D、4句

A、由n个顶点构成的边的权值之和最小的连通子图

B、由n-1条权值之和最小的边构成的子图

C、由n-1条权值之和最小的边构成的连通子图

D、由n-1条权值最小的边构成的子图

求图的中心点。设V是有向图G的一个顶点， V的偏心度定义为： Find the central point of the graph. Let V be a vertex of the graph G, the definition of the eccentricity of V is: max{dist(w,v),?w∈V(G)} 如果v是有向图G中具有最小偏心度的顶点，则称顶点v是G的中心点。 If the eccentricity of v is minimal in the graph G, then we call V a central point of G. 请从以下代码语句中选择正确的5条，填入空白处。按空白的标号顺序依次列出代码语句的标号,用一个空格分隔。如A F D H C Please choose 5 statements from the following, and put them into the blanks. List the number of the statement you choose according to the order of the blanks, and separate them with a single blank space. For instance, A F D H C. C++代码： void FLOYD_PXD(AdjMatrix g){ // 对以带权邻接矩阵表示的有向图g，求其中心点。 AdjMatrix w = g; for(k = 1; k <= n; k++) for(i="1;" i++) for(j="1;" j j++) if( (1) ) (2) ; v="1;" dist="MAXINT;" j++){ s="0;" i (3) (4) ){ (5) } for printf("有向图g的中心点是顶点%d,偏心度%d\n", v, dist); }python代码：def floyd_pxd(adjmatrix g): adjmatrix w="g" k in range(1, n+1): range (1, if ( ): print("有向图g的中心点是" + str(v) ",顶点偏心度" str(dist)) 选项： src="http://static.jiandati.com/a9585d5-chaoxing2016-284362.png">