第5课 图101106

第五课 图

一、选择题

1．图中有关路径的定义是（ ）。

A．由顶点和相邻顶点序偶构成的边所形成的序列 B．由不同顶点所形成的序列 C．由不同边所形成的序列 D．上述定义都不是 参考答案：A

2．设无向图的顶点个数为n，则该图最多有（ ）条边。

A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 E．n2 参考答案：B

备注：设有向图的顶点个数为n，则该图最多有n(n-1)条边。

3．一个n个顶点的连通无向图，其边的个数至少为（ ）。

A．n-1 B．n C．n+1 D．nlogn 参考答案：A

4．要连通具有n个顶点的有向图，至少需要（ ）条边。

A．n-l B．n C．n+l D．2n 参考答案：B

5．n个结点的完全有向图含有边的数目（ ）。

A．n*n Ｂ．n（n+1） C．n／2 D．n*（n-1） 参考答案：D

6．一个有n个结点的图，最少有（ ）个连通分量。

A．0 B．1 C．n-1 D．n 参考答案：B

7．一个有n个结点的图，最多有（ ）个连通分量。

A．0 B．1 C．n-1 D．n 参考答案：D

8．用有向无环图描述表达式(A+B)*（（A+B）/A），至少需要顶点的数目为（ ）。

A．5 B．6 C．8 D．9 参考答案：A 9．用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是（A．逆拓扑有序 B．拓扑有序 C．无序的 参考答案：A

10．下面结构中最适于表示稀疏无向图的是（ ）。

A．邻接矩阵 B．逆邻接表 C．邻接多重表 D．十字链表 E．邻接表 参考答案：C

11．下列哪一种图的邻接矩阵是对称矩阵？（ ）

。 ）

A．有向图 B．无向图 C．AOV网 D．AOE网 参考答案：B

12．当一个有N个顶点的图用邻接矩阵A表示时，顶点Vi的度是（ ）。

A．

?A[i,j]i?1n B．

?A?i,j?j?1n C．

?A[j,i]i?1n D．

?A[i,j]?A?j,i?i?1nn+

j?1

参考答案：B

13．下列说法不正确的是（ ）。

A．图的遍历是从给定的源点出发每一个顶点仅被访问一次 B．遍历的基本算法有两种：深度遍历和广度遍历 C．图的深度遍历不适用于有向图 D．图的深度遍历是一个递归过程 参考答案：C

14．无向图G=(V,E),其中：

V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（ ）。

A．a,b,e,c,d,f B．a,c,f,e,b,d C．a,e,b,c,f,d D．a,e,d,f,c,b 参考答案：D

15．设图如右所示， ，在下面的5个序列中，符合深度优先遍历的序列有（ ）个。

a e b d f c a c f d e b a e d f c b a e f d c b a e f d b c

A．5个 B．4个 C．3个 D．2个 参考答案：D

16．下列方法中可以判断出一个有向图是否有环（回路）的是（ ）。

A．广度优先遍历 B．拓扑排序 C．求最短路径 D．求关键路径 参考答案：B

17．下列方法中可以判断出一个有向图是否有环（回路）的是（ ）。

A．深度优先遍历 B．广度优先遍历 C．求最短路径 D．求关键路径 参考答案：A

18．在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为（ ）。

A．O(n) B．O(n+e) C．O(n2) D．O(n3) 参考答案：B

19．当各边上的权值（ ）时，BFS算法可用来解决单源最短路径问题。

A．均相等 B．均互不相等 C．不一定相等

参考答案：A

20．求解最短路径的Floyd算法的时间复杂度为（ ）。

A．O（n） B．O（n+c） C．O（n*n） D．O（n*n*n） 参考答案：D

21．已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={,,,, ,,,,}，G的拓扑序列是（ ）。

A．V1,V3,V4,V6,V2,V5,V7 B．V1,V3,V2,V6,V4,V5,V7 C．V1,V3,V4,V5,V2,V6,V7 D．V1,V2,V5,V3,V4,V6,V7

参考答案：A

22．若一个有向图的邻接矩阵中，主对角线以下的元素均为零，则该图的拓扑有序序列（ ）。

A．存在 B．不存在 参考答案：A

23．一个有向无环图的拓扑排序序列（ ）是唯一的。

A．一定 B．不一定 参考答案：A

24．在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（ ）。

A．G中有弧 B．G中有一条从Vi到Vj的路径 C．G中没有弧 D．G中有一条从Vj到Vi的路径 参考答案：D

25．在用邻接表表示图时，拓扑排序算法时间复杂度为（ ）。

A．O(n) B．O(n+e) C．O(n*n) D．O(n*n*n) 参考答案：B

26．关键路径是事件结点网络中（ ）。

A．从源点到汇点的最长路径 B．从源点到汇点的最短路径 C．最长回路 D．最短回路 参考答案：A

27．下面关于求关键路径的说法不正确的是（ ）。 A．求关键路径是以拓扑排序为基础的

B．一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同

C．一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差

D．关键活动一定位于关键路径上 参考答案：C

28．下列关于AOE网的叙述中，不正确的是（ ）。

A．关键活动不按期完成就会影响整个工程的完成时间

B．任何一个关键活动提前完成，那么整个工程将会提前完成 C．所有的关键活动提前完成，那么整个工程将会提前完成 D．某些关键活动提前完成，那么整个工程将会提前完成

参考答案：B

29．在一个无向图中，所有顶点的度数之和等于所有边数（ ）倍。

A．1/2 B．2 C．1 D．4 参考答案：B

30．在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ ）倍。

A．1/2 B．2 C．1 D．4 参考答案：C

二、应用题 1．

（1）如果G1是一个具有n个顶点的连通无向图，那么G1最多有多少条边？G1最少有多少条边？ 参考答案：G1最多n(n-1)/2条边，最少n-1条边。

（2）如果G2是一个具有n个顶点的强连通有向图，那么G2最多有多少条边？G2最少有多少条边？ 参考答案：G2最多n(n-1)条边，最少n条边。

2．n个顶点的无向连通图最少有多少条边？n个顶点的有向连通图最少有多少条边？ 参考答案：n-1，n

3．证明：具有n个顶点和多于n-1条边的无向连通图G一定不是树。 参考答案：

具有n个顶点n-1条边的无向连通图是自由树，即没有确定根结点的树，每个结点均可当根。若边数多于n-1条，因一条边要连接两个结点，则必因加上这一条边而使两个结点多了一条通路，即形成回路。

4．用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边的条数是否有关？ 参考答案：

设图的顶点个数为n(n≥0)，则邻接矩阵元素个数为n2，即顶点个数的平方，与图的边数无关。

5．请回答下列关于图(Graph)的一些问题：

（1）有n个顶点的有向强连通图最多有多少条边?最少有多少条边?

（2）表示有1000个顶点、l000条边的有向图的邻接矩阵有多少个矩阵元素？是否稀疏矩阵？ （3）对于一个有向图，不用拓扑排序，如何判断图中是否存在环？ 参考答案： （1）n(n-1)，n

（2）106，不一定是稀疏矩阵（稀疏矩阵的定义是非零个数远小于该矩阵元素个数，且分布无规律）

（3）使用深度优先遍历，按退出DFS过程的先后顺序记录下的顶点是逆向拓扑有序序列。若在执行DFS (v)未退出前，出现顶点u到v的回边，则说明存在包含顶点v和顶点u的环。

6．设有数据逻辑结构为：B = (K, R), K = {k1, k2, ?, k9}

R={, , ,, , ,, , , , }

（1）画出这个逻辑结构的图示。

（2）相对于关系r，指出所有的开始接点和终端结点。

（3）分别对关系r中的开始结点，举出一个拓扑序列的例子。

（4）分别画出该逻辑结构的正向邻接表和逆向邻接表。 参考答案： （1）略。

（2）开始结点：（入度为0）K1，K2，终端结点（出度为0）K6，K7。 （3）拓扑序列K1，K2，K3，K4，K5，K6，K8，K9，K7

K2，K1，K3，K4，K5，K6，K8，K9，K7

规则：开始结点为K1或K2，之后，若遇多个入度为0的顶点，按顶点编号顺序选择。 （4）略。

7．有向图的邻接表存储如下，要求：（1）画出其邻接矩阵存储；（2）写出图的所有强连通分量；（3）写出顶点a到顶点i的全部简单路径。

参考答案：

（1）略。（注：邻接矩阵下标按字母升序:abcdefghi）

（2）强连通分量：（a），(d)，（h），(b，e，i，f，c，g）

（3）顶点a到顶点i的简单路径：（a->b->e->i），（a->c->g->i），（a->c->b->e->i）。

8．如何对有向图中的顶点号重新安排可使得该图的邻接矩阵中所有的1都集中到对角线以上？ 参考答案：

按各顶点的出度进行排序。n个顶点的有向图，其顶点最大出度是n-1，最小出度为0。这样排序后，出度最大的顶点编号为1，出度最小的顶点编号为n。之后，进行调整，即若存在弧，而顶点j的出度大于顶点i的出度，则将把j编号在顶点i的编号之前。

9．首先将如下图所示的无向图给出其存储结构的邻接链表表示，然后写出对其分别进行深度，广度优先遍历的结果。

参考答案：

深度优先遍历序列：125967384；宽度优先遍历序列：123456789。

注：（1）邻接表不唯一，这里顶点的邻接点按升序排列；（2）在邻接表确定后，深度优先和宽度优先遍历序列唯一；（3）这里的遍历，均从顶点1开始。

10．下面的邻接表表示一个给定的无向图，

（1）给出从顶点v1开始，对图G用深度优先搜索法进行遍历时的顶点序列； （2）给出从顶点v1开始，对图G用广度优先搜索法进行遍历时的顶点序列。

参考答案：（1）V1V2V4V3V5V6；（2）V1V2V3V4V5V6。

11．设G=(V,E)以邻接表存储，如图所示，试画出图的深度优先和广度优先生成树。

234?1

5?1342

124?3

12 35?4 24?5

参考答案：

深度优先生成树：

广度优先生成树：

12．对一个图进行遍历可以得到不同的遍历序列，那么导致得到的遍历序列不唯一的因素有哪些？ 参考答案：

遍历不唯一的因素有：开始遍历的顶点不同；存储结构不同；在邻接表情况下邻接点的顺序不同。

13．某田径赛中各选手的参赛项目表如下: 姓名 参 赛 项 ZHAO A B E QIAN C D SHUN C E F LI D F A ZHOU B F 设项目A,B ,?，F各表示一数据元素，若两项目不能同时举行，则将其连线(约束条件)。 （1）根据此表及约束条件画出相应的图状结构模型，并画出此图的邻接表结构； （2）写出从元素A出发按“广度优先搜索”算法遍历此图的元素序列。 参考答案：

（1）

（2）AFEDBC或ABDEFC。

14．已知无向图如下所示：（1）给出从V1开始的广度优先搜索序列；（2）画出它的邻接表；（3）画出从V1开始深度优先搜索生成树。

参考答案：

设邻接表（略）中顶点的邻接点按顶点编号升序排列（V1编号为1），广度优先搜索序列：V1V2V3V4V5V6V7V8；深度优先搜索序列：V1V2V4V8V5V3V6V7。

15．已知某图的邻接表为

v1v2v3v4v5v6211124?35563????4? （1）写出此邻接表对应的邻接矩阵；

（2）写出由v1开始的深度优先遍历的序列； （3）写出由v1开始的深度优先的生成树； （4）写出由v1开始的广度优先遍历的序列； （5）写出由v1开始的广度优先的生成树；

（6）写出将无向图的邻接表转换成邻接矩阵的算法。 参考答案： （1）略。

（2）V1V2V5V3V4V6

（3）

（4）V1V2V3V4V5V6

（5）

（6）void AdjListToAdjMatrix(AdjList gl, AdjMatrix gm)

//将图的邻接表表示转换为邻接矩阵表示。

{for (i=1;i<=n;i++) //设图有n个顶点，邻接矩阵初始化。 for (j=1;j<=n;j++) gm[i][j]=0; for (i=1;i<=n;i++)

{p=gl[i].firstarc; //取第一个邻接点。

while (p!=null) {gm[i][p->adjvex]=1;p=p->next; }//下一个邻接点 }//for }//算法结束

16．考虑右图：

（1）从顶点A出发，求它的深度优先生成树； （2）从顶点E出发，求它的广度优先生成树；

（3）根据普利姆（Prim）算法，求它的最小生成树。 参考答案：

设该图用邻接表存储结构存储，顶点的邻接点按顶点编号升序排列

（1）ABGFDEC

（2）EACFBDG

（3）

17．在什么情况下，Prim算法与Kruskual算法生成不同的MST？ 参考答案：

在有相同权值边时生成不同的MST，在这种情况下，用Prim或Kruskal也会生成不同的MST。

18．已知一个无向图如下图所示，要求分别用Prim和Kruskal算法生成最小树（假设以①为起点，试画出构造过程）。

参考答案：

Prim算法构造最小生成树的步骤：(1,6),(1,5),(6,2),(2,3),(3,4)

Kruskal算法，构造最小生成树过程：(2,3),(3,4) (或(2,4)),(1,6),(5,6)（或(1，5)）,(2,6)

19．G=(V,E)是一个带有权的连通图，则：

（1）请回答什么是G的最小生成树；

（2）G为下图所示，请找出G的所有最小生成树。 参考答案：

（2）2棵：和

20．试写出用克鲁斯卡尔（Kruskal）算法构造下图的一棵最小生成树的过程。

参考答案：

V（G）={1，2，3，4，5，6，7}

E（G）={（1，6，4），（1，7，6），（2，3，5），（2，4，8），（2，5，12），（

21．求出下图的最小生成树。

1，2，18）}

参考答案：

V（G）={1，2，3，4，5，6，7，8}

E（G）={（3，8，2），（4，7，2），（3，4，3），（5，8，3），（2，5，4），（6，7，4），（1，2，5）}

注：（或将（3，4，3）换成（7，8，3））

22．一带权无向图的邻接矩阵如下图 ，试画出它的一棵最小生成树。

参考答案：

设顶点集合为{1，2，3，4，5，6}，由右边的逻辑图可以看出，在{1，2，3}和{4，5，

6}回路中，各任选两条边，加上（2，4），则可构成9棵不同的最小生成树。

23．下图表示一个地区的通讯网，边表示城市间的通讯线路，边上的权表示架设线路花费的代价，如何选择能沟通每个城市且总代价最省的n-1条线路，画出所有可能的选择。

参考答案：

V(G)={1,2,3,4,5,6}

E1(G)={（1，2，16），（2，3，5），（2，6，6），（2，4，11），（6，5，18）}， E2(G)={（1，2，16），（2，3，5），（3，6，6），（2，4，11），（6，5，18）}

24．设无向网G如下：

{if(pre==null)g[i].firstarc=p->next;else pre->next=p->next;free(p);}//释放结点空间。 else {pre=p; p=p->next;} //沿链表继续查找 p=g[j].firstarc; pre=null; //删顶点j 的边结点(j,i) while (p)

if (p->adjvex==i)

{if(pre==null)g[j].firstarc=p->next;else pre->next=p->next;free(p);}//释放结点空间。 else {pre=p; p=p->next;} //沿链表继续查找 }// DeletEdge

算法中假定给的i，j均存在，否则应检查其合法性。若未给顶点编号，而给出顶点信息，则先用顶点定位函数求出其在邻接表顶点向量中的下标i和j。

8．假设有向图以邻接表存储，试编写算法删除弧的算法。 参考答案：

void DeleteArc（AdjList g,vertype vi, vertype vj）

//删除以邻接表存储的有向图g的一条弧，假定顶点vi和vj存在 {i=GraphLocateVertex(g,vi); j=GraphLocateVertex(g,vj); //顶点定位 p=g[i].firstarc; pre=null; while (p)

if (p->adjvex==j)

{if(pre==null) g[i].firstarc=p->next;else pre->next=p->next;free(p);}//释放结点空间。 else { pre=p; p=p->next;} }

9．设有向图用邻接表表示，图有n个顶点，表示为1至n，试写一个算法求顶点k的入度(1

在有向图的邻接表中，求顶点的出度容易，只要简单在该顶点的邻接点链表中查结点个数即可。而求顶点的入度，则要遍历整个邻接表。 参考答案：

int count (AdjList g , int k )

//在n个顶点以邻接表表示的有向图g中，求指定顶点k(1<=k<=n)的入度。 {

int count =0;

for (i=1;i<=n;i++) //求顶点k的入度要遍历整个邻接表。 if(i!=k) //顶点k的邻接链表不必计算 {

p=g[i].firstarc;//取顶点 i 的邻接表。 while (p)

{if (p->adjvex==k) count++; p=p->next; }//while }//if

return(count); //顶点k的入度. }

10．试编写求无向图G的连通分量的算法。要求输出每一连通分量的顶点值。(设图G已用邻接表存储) 参考答案：

使用图的遍历可以求出图的连通分量。进入dfs或bfs一次，就可以访问到图的一个连通分量的所有顶点。 void dfs () {

visited[v]=1; printf ( “=”,v); //输出连通分量的顶点。 p=g[v].firstarc; while (p!=null)

{if（visited[p->adjvex==0]） dfs(p->adjvex); p=p->next; }//while }// dfs

void Count()

//求图中连通分量的个数

{int k=0 ; static AdjList g ; //设无向图g有n个结点 for (i=1;i<=n;i++ )

if (visited[i]==0) { printf (\第%d个连通分量:\\n\}//Count

算法中visited[]数组是全程变量，每个连通分量的顶点集按遍历顺序输出。这里设顶点信息就是顶点编号，否则应取其g[i].vertex分量输出。

11．设无向图G已用邻接表结构存储，顶点表为GL[n] (n为图中顶点数)，试用“广度优先搜索”方法，写出求图G中各连通分量的C语言描述算法：BFSCOM(GL)。（注：算法中可调用队列操作的基本算法。） 参考答案：

void bfs(AdjList GL，vertype v )

//从v发广度优先遍历以邻接表为存储结构的无向图GL。 {

visited[v]=1;

printf( \输出第一个遍历的顶点。

QueueInit(Q); QueueIn(Q ,v); //先置空队列，然后第一个顶点v入队列，设队列容量足够大 while (!QueueEmpty(Q))

{v=QueueOut(Q); p=GL[v].firstarc; //GL是全局变量， v入队列。 while (p!=null)

{if(visited[p->adjvex]==0)

{printf(\p=p->next; }//while

}// while (!QueueEmpty(Q)) }//bfs

void BFSCOM()

//广度优先搜索，求无向图Ｇ的连通分量。 { int count=0; //记连通分量个数。

for (i=1;i<=n;i++) visited[i]=0; for (i=1;i<=n;i++)

if (visited[i]==0) {printf(\第%d个连通分量:\\n\}//BFSCOM

12．写出图的深度优先搜索DFS算法的非递归算法。

参考答案：

void Traver(AdjList g,vertype v)

//图g以邻接表为存储结构，算法从顶点v开始实现非递归深度优先遍历。 {struct arc *stack[];

visited[v]=1;printf(v); //输出顶点v top=0; p=g[v].firstarc; stack[++top]=p; while(top>0 || p!=null) {while (p)

if (p && visited[p->adjvex]) p=p->next;

else {printf(p->adjvex); visited[p->adjvex]=1; stack[++top]=p; p=g[p->adjvex].firstarc; }//else

if (top>0) {p=stack[top--]; p=p->next; } }//while }//算法结束。

以上算法适合连通图，若是非连通图，则再增加一个主调算法，其核心语句是 for (vi=1;vi<=n;vi++) if (!visited[vi]) Traver(g,vi);

13．设计算法以实现对无向图G的深度遍历，要求：将每一个连通分量中的顶点以一个表的形式输出。例如，下图的输出结果为：（1，3）（2，6，7，4，5，8）（9，10）

（注：本算法中可以调用以下几个函数：

firstadj（g,v）——返回图g中顶点v的第一个邻接点的号码，若不存在，则返回0；

nextadj（g,v,w）——返回图g中顶点v的邻接点中处于w之后的邻接点的号码，若不存在，则返回0。 nodes（g）——返回图g中的顶点数） 参考答案：

本题是对无向图Ｇ的深度优先遍历，dfs算法见前述。这里仅给出将连通分量的顶点用括号括起来的算法。为了得出题中的输出结果，各顶点的邻接点要按升序排列。 void Traver( )

{for (i=1;i<=nodes(g);i++) visited[i]=0; //visited是全局变量，初始化。 for (i=1;i<=nodes(g);i++)

if (visied[i]==0) {printf (\}//Traver

14．设计算法以判断给定的无向图G中是否存在一条以V0为起点的包含所有顶点的简单路径，若存在，返回TRUE，否则，返回FALSE（注：本算法中可以调用以下几个函数：FIRSTADJ（G，V）——返回图G中顶点V的第一个邻接点的号码，若不存在，则返回0；NEXTADJ（G，V，W）——返回图G中顶点V的邻接点中处于W之后的邻接点的号码，若不存在，则返回0；NODES（G）——返回图G中的顶点数）

参考答案：

本题应使用深度优先遍历。设图的顶点信息就是顶点编号，用num记录访问顶点个数，当num等于图的顶点个数（题中的NODES(G)），输出所访问的顶点序列，顶点序列存在path中，path和visited数组，顶点计数器num，均是全局变量，都已初始化。

void SPathdfs(v0)

//判断无向图Ｇ中是否存在以v0为起点，包含图中全部顶点的简单路径。 {

visited[v0]=1; path[++num]=v0;

if (num==nodes(G)) //有一条简单路径，输出之。

{for (i=1;i<=num;i++) printf( \p=g[v0].firstarc; while (p)

{if (visited[p->adjvex]==0) SPathdfs(p->adjvex); //深度优先遍历。 p=p->next; //下一个邻接点。 }//while

visited[v0]=0; num--; //取消访问标记，使该顶点可重新使用。 }//SPathdfs

15．已有邻接表表示的有向图，

请编程判断从第u顶点至第v顶点是否有简单路径，若有则印出该路径上的顶点。要求：先描述图的存储结构，并简述算法思路；查找邻接点等图的运算要自己实现。（尽量采用非递归算法） 参考答案：

非递归算法，顶点信息仍是编号。

void AllSPdfs(AdjList g,vertype u,vertype v)

//求有向图g中顶点u到顶点v的所有简单路径，初始调用形式：AllSPdfs(g,u,v) { int top=0,s[];

s[++top]=u; visited[u]=1; while (top>0 || p)

{p=g[s[top]].firstarc; //第一个邻接点。

while (p!=null && visited[p->adjvex]==1) p=p->next; //下一个访问邻接点表。 if (p==null) top--; //退栈。

else { i=p->adjvex; //取邻接点（编号）。

if (i==v) //找到从u到v的一条简单路径，输出。

{for (k=1;k<=top;k++) printf( \else { visited[i]=1; s[++top]=i; } //else深度优先遍历。 }//else }//while }// AllSPdfs

16．图的D_搜索类似与BFS，不同之处在于使用栈代替BFS中的队列，入出队列的操作改为入出栈的操作，即当一个顶点的所有邻接点被搜索之后，下一个搜索出发点应该是最近入栈(栈顶)的顶点。

（1）用邻接表做存储结构，写一个D_搜索算法；

（2）用D_搜索方法的访问次序和相应的生成树，当从某顶点出发搜索它的邻接点，请按邻接点序号递增序搜索，以使答案唯一。 参考答案：

（1）D_搜索类似BFS，只是用栈代替队列，入出队列改为入出栈。查某顶点的邻接点时，若其邻接点尚未遍历，则遍历之，并将其压入栈中。当一个顶点的所有邻接点被搜索后，栈顶顶点是下一个搜索出发点。 void D_BFS(AdjList g ,vertype v0)

// 从v0顶点开始，对以邻接表为存储结构的图g进行D_搜索。

{ int s[], top=0; //栈，栈中元素为顶点，仍假定顶点用编号表示。 for (i=1;i<=n;i++) visited[i]=0; //图有n个顶点，visited数组为全局变量。 for (i=1;i<=n;i++) //对n个顶点的图g进行D_搜索。 if (visited[i]==0)

{s[++top]=i; visited[i]=1; printf( \while (top>0) {i=s[top--]; //退栈

p=g[i].firstarc; //取第一个邻接点

while (p!=null) //处理顶点的所有邻接点 {j=p->adjvex;

if (visited[j]==0) //未访问的邻接点访问并入栈。 {visited[j]=1; printf( \p=p->next;

} //下一个邻接点 }//while(top>0) } //if

}//D_BFS

（2）D_搜索序列：1234675，生成树如图：

17．我们可用“破圈法”求解带权连通无向图的一棵最小代价生成树。所谓“破圈法”就是“任取一圈，去掉圈上权最大的边”，反复执行这一步骤，直到没有圈为止。请给出用“破圈法”求解给定的带权连通无向图的一棵最小代价生成树的详细算法，并用程序实现你所给出的算法。注：圈就是回路。 参考答案：

连通图的生成树包括图中的全部n个顶点和足以使图连通的n-1条边，最小生成树是边上权值之和最小的生成树。故可按权值从大到小对边进行排序，然后从大到小将边删除。每删除一条当前权值最大的边后，就去测试图是否仍连通，若不再连通，则将该边恢复。若仍连通，继续向下删；直到剩n-1条边为止。

void SpnTree (AdjList g)

//用“破圈法”求解带权连通无向图的一棵最小代价生成树。 {

typedef struct {int i,j,w}node; //设顶点信息就是顶点编号，权是整型数 node edge[];

scanf( \输入边数和顶点数。 for (i=1;i<=e;i++) //输入e条边：顶点，权值。

scanf(\

for (i=2;i<=e;i++) //按边上的权值大小，对边进行逆序排序。 {edge[0]=edge[i]; j=i-1;

while (edge[j].w

k=1; eg=e;

while (eg>=n) //破圈，直到边数e=n-1. {if (connect(k)) //删除第k条边若仍连通。

{edge[k].w=0; eg--; }//测试下一条边edge[k]，权值置0表示该边被删除 k++; //下条边 }//while

}//算法结束。

connect()是测试图是否连通的函数，可用图的遍历实现，若是连通图，一次进入dfs或bfs就可遍历完全部结点，否则，因为删除该边而使原连通图成为两个连通分量时，该边不应删除。前面第17,18题就是测连通分量个数的算法，请参考。“破圈”结束后，可输出edge中w不为０的n-1条边。

18．已知个n顶点的有向图，用邻接矩阵表示，编写函数计算每对顶点的最短路径。 参考答案：

本题用FLOYD算法直接求解如下： void ShortPath_FLOYD(AdjMatrix g)

//求具有n个顶点的有向图每对顶点间的最短路径

{AdjMatrix length; //length[i][j]存放顶点vi到vj的最短路径长度。 for (i=1;i<=n;i++)

for (j=1;j<=n;j++) length[i][j]=g[i][j]; //初始化。 for (k=1;k<=n;k++) for (i=1;i<=n;i++)

for (j=1;j<=n;j++)

if (length[i][k]+length[k][j]

length[i][j]=length[i][k]+length[k][j]; }

19．欲用四种颜色对地图上的国家涂色，有相邻边界的国家不能用同一种颜色（点相交不算相邻）。（1）试用一种数据结构表示地图上各国相邻的关系；（2）描述涂色过程的算法。 参考答案：

地图涂色问题可以用“四染色“定理。将地图上的国家编号（1到n），从编号1开始逐一涂色，对每个区域用1色，2色，3色，4色（下称“色数”）依次试探，若当前所取颜色与周围已涂色区域不重色，则将该区域颜色进栈；否则，用下一颜色。若1至4色均与相邻某区域重色，则需退栈回溯,修改栈顶区域的颜色。用邻接矩阵数据结构C[n][n]描叙地图上国家间的关系。n个国家用n阶方阵表示，若第i个国家与第j个国家

相邻，则Cij=1，否则Cij=0。用栈s记录染色结果，栈的下标值为区域号，元素值是色数。 void MapColor(AdjMatrix C)

//以邻接矩阵C表示的n个国家的地区涂色 {

int s[]; //栈的下标是国家编号，内容是色数 s[1]=1; //编号01的国家涂1色 i=2;j=1; //i为国家号，j为涂色号 while (i<=n)

{ while (j<=4 && i<=n) {

k=1; //k指已涂色区域号

while (k

//与相邻区不重色，涂色结果进栈，继续对下一区涂色进行试探 }//while (j<=4 && i<=n)

if (j>4) {i--; j=s[i]+1;} //变更栈顶区域的颜色。 }//while(i<=n) }//结束MapColor

20．设有向图Ｇ以邻接表形式存储，试基于图的深度优先遍历方法设计一算法，用以判定图中是否存在从顶点vi到顶点vj的路径（i≠j）。 参考答案：

从顶点vi出发进行深度优先遍历，调用完成时所有与vi有路径相通的顶点都被访问到。 Boolean Path(ALGraph G,int i,int j){

//若有向图G中从顶点vi到顶点vj有路径相通，则返回TRUE，否则返回FALSE for(k=0;k

if (visited[j]) return TRUE; else return FALSE; }//Path

void DFS(ALGraph G,int i){//从顶点vi出发对图Ｇ进行深度优先遍历 visited[i]=TRUE;

for(p=G.vertices[i].firstarc;p;p=p->next)

//从顶点vi的未被访问的邻接点出发深度优先遍历图Ｇ if (!visited[p->adj]) DFS(G,p->adj); }//DFS

21．设有向图Ｇ以邻接表形式存储，试基于图的广度优先遍历方法设计一算法，用以判定图中是否存在从顶点vi到顶点vj的路径（i≠j）。 参考答案：

int exist_path_BFS(ALGraph G,int i,int j){ int visited[MAXSIZE]; InitQueue(Q); EnQueue(Q,i);

while(!QueueEmpty(Q)) {

DeQueue(Q,u); visited[u]=1;

for(p=G.vertices[i].firstarc;p;p=p->nextarc) { k=p->adjvex; if(k==j) return 1;

if(!visited[k]) EnQueue(Q,k); }//for }//while return 0;

}//exist_path_BFS

22．试无向图采用邻接表存储结构，试设计算法，判定图中任意给定的两个顶点间是否存在一条长为k的简单路径。 参考答案：

设要判定结点i和结点j间是否存在长为k的简单路径，则只需判定结点i的邻接点l和结点j间是否存在长为k-1的简单路径。 int visited[MAXSIZE];

int exist_path_len(ALGraph G,int i,int j,int k){

if(i==j&&k==0) return 1; //找到了一条路径,且长度符合要求 else if(k>0) { visited[i]=1;

for(p=G.vertices[i].firstarc;p;p=p->nextarc) { l=p->adjvex; if(!visited[l])

if(exist_path_len(G,l,j,k-1)) return 1; //剩余路径长度减一 }//for

visited[i]=0; //本题允许曾经被访问过的结点出现在另一条路径中 }//else

return 0; //没找到 }//exist_path_len

23．已知有向图G中两个顶点u和v，试编写算法求图中从u到v的所有简单路径。 参考答案：

int path[MAXSIZE],visited[MAXSIZE]; //暂存遍历过程中的路径 int Find_All_Path(ALGraph G,int u,int v,int k) {

//初次调用时传入的参数应为G,u,v,0 path[k]=u; //加入当前路径中 visited[u]=1; if(u==v)

{ //找到了一条简单路径 printf(\

for(i=0;path[i];i++) printf(\ //打印输出 } else

for(p=G.vertices[u].firstarc;p;p=p->nextarc)

{

l=p->adjvex;

if(!visited[l]) Find_All_Path(G,l,v,k+1); //继续寻找 }

visited[u]=0;

path[k]=0; //回溯 }//Find_All_Path