《数据结构》期末考试复习题 第7章 图

第七章 图

一、选择题

1．图中有关路径的定义是（ ）。【北方交通大学 2001 一、24 （2分）】

A．由顶点和相邻顶点序偶构成的边所形成的序列 B．由不同顶点所形成的序列 C．由不同边所形成的序列 D．上述定义都不是 2．设无向图的顶点个数为n，则该图最多有（ ）条边。

2

A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 E．n 【清华大学 1998 一、5 （2分）】【西安电子科技大 1998 一、6 （2分）】 【北京航空航天大学 1999 一、7 （2分）】

3．一个n个顶点的连通无向图，其边的个数至少为（ ）。【浙江大学 1999 四、4 (4分)】

A．n-1 B．n C．n+1 D．nlogn； 4．要连通具有n个顶点的有向图，至少需要（ ）条边。【北京航空航天大学 2000 一、6(2分）】

A．n-l B．n C．n+l D．2n 5．n个结点的完全有向图含有边的数目（ ）。【中山大学 1998 二、9 （2分）】

A．n*n Ｂ．n（n＋１） C．n／2 D．n*（n－l）

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

A．0 B．1 C．n-1 D．n 【北京邮电大学 2000 二、5 （20/8分）】

7．在一个无向图中，所有顶点的度数之和等于所有边数（ ）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ ）倍。【哈尔滨工业大学 2001 二、3 （2分）】

A．1/2 B．2 C．1 D．4 8．用有向无环图描述表达式(A+B)*（（A+B）/A），至少需要顶点的数目为( )。【中山大学1999一、14】

A．5 B．6 C．8 D．9

9．用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是( )。

A．逆拓扑有序 B．拓扑有序 C．无序的 【中科院软件所 1998】

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

A．邻接矩阵 B．逆邻接表 C．邻接多重表 D．十字链表 E．邻接表

【北京工业大学 2001 一、3 (2分)】

11．下列哪一种图的邻接矩阵是对称矩阵？（ ）【北方交通大学 2001 一、11 （2分）】

A．有向图 B．无向图 C．AOV网 D．AOE网

?0A???1??01010?1???0?12． 从邻接阵矩可以看出，该图共有（①）个顶点；如果是有向图该图共有

（②） 条弧；如果是无向图，则共有（③）条边。【中科院软件所 1999 六、2（3分）】

①．A．9 B．3 C．6 D．1 E．以上答案均不正确 ②．A．5 B．4 C．3 D．2 E．以上答案均不正确 ③．A．5 B．4 C．3 D．2 E．以上答案均不正确

13．当一个有N个顶点的图用邻接矩阵A表示时，顶点Vi的度是（ ）。【南京理工大学1998一、4(2分）】

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

14．用相邻矩阵A表示图，判定任意两个顶点Vi和Vj之间是否有长度为m 的路径相连，则只要检查（ ）的第i行第j列的元素是否为零即可。【武汉大学 2000 二、7】

m

A．mA B．A C．A D．Am-1 15. 下列说法不正确的是（ ）。【青岛大学 2002 二、9 （2分）】

A．图的遍历是从给定的源点出发每一个顶点仅被访问一次 C．图的深度遍历不适用于有向图

B．遍历的基本算法有两种：深度遍历和广度遍历 D．图的深度遍历是一个递归过程 16．无向图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)}，对该图进行深度优先遍历，得到的顶点序列正确的是（ ）。【南京理工大学 2001 一、14 （1.5分）】

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 17. 设图如右所示，在下面的5个序列中，符合深度优先遍历的序列有多少？（ ）

【南京理工大学 2000 一、20 （1.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个 a

bec

df

第17题图 第18题图

18.下图中给出由7个顶点组成的无向图。从顶点1出发，对它进行深度优先遍历得到的序列是( ① )，而进行广度优先遍历得到的顶点序列是（ ② ）。【中科院软件所 1999 六、2-（1）（2分）】

①．A．1354267 B．1347652 C．1534276 D．1247653 E．以上答案均不正确

②．A．1534267 B．1726453 C．l354276 D．1247653 E．以上答案均不正确

19．下面哪一方法可以判断出一个有向图是否有环（回路）：【东北大学 2000 4、2（4分）】

A．深度优先遍历 B. 拓扑排序 C. 求最短路径 D. 求关键路径

20. 在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为( )。

23

A. O(n) B. O(n+e) C. O(n) D. O(n) 【合肥工业大学 2001 一、2 （2分）】 21. 下面是求连通网的最小生成树的prim算法：集合VT，ET分别放顶点和边，初始为（ 1 ），

下面步骤重复n-1次: a：（ 2 ）；b：（ 3 ）；最后：（ 4 ）。【南京理工大学 1997 一、11_14 （8分）】

（1）．A．VT，ET为空 B．VT为所有顶点，ET为空 C．VT为网中任意一点，ET为空 D．VT为空，ET为网中所有边

（2）．A. 选i属于VT，j不属于VT，且（i，j）上的权最小 B．选i属于VT，j不属于VT，且（i，j）上的权最大 C．选i不属于VT，j不属于VT，且（i，j）上的权最小 D．选i不属于VT，j不属于VT，且（i，j）上的权最大

（3）．A．顶点i加入VT，（i,j）加入ET B. 顶点j加入VT，（i,j）加入ET C. 顶点j加入VT，（i,j）从ET中删去 D．顶点i,j加入VT，（i,j）加入ET

（4）．A．ET 中为最小生成树 B．不在ET中的边构成最小生成树 C．ET中有n-1条边时为生成树，否则无解 D．ET中无回路时，为生成树，否则无解

22. (1). 求从指定源点到其余各顶点的迪杰斯特拉（Dijkstra）最短路径算法中弧上权不能为负的原因是在实际应用中无意义；

3

(2). 利用Dijkstra求每一对不同顶点之间的最短路径的算法时间是O(n ) ；（图用邻接矩阵表示）

(3). Floyd求每对不同顶点对的算法中允许弧上的权为负，但不能有权和为负的回路。 上面不正确的是（ ）。【南京理工大学 2000 一、21 （1.5分）】

A．(1),(2),(3) B．(1) C．(1),(3) D．(2),(3) 23．当各边上的权值( )时，BFS算法可用来解决单源最短路径问题。【中科院计算所2000一、3 (2分）】

A．均相等 B．均互不相等 C．不一定相等 24. 求解最短路径的Floyd算法的时间复杂度为( )。【合肥工业大学 1999 一、2 （2分）】

A．O（n） B. O（n+c） C. O（n*n） D. O（n*n*n） 25．已知有向图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 【北京航空航天大学 2000 一、7 （2分）】

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

A．存在 B．不存在【中科院计算所1998 二、6 (2分）】【中国科技大学 1998二、6（2分）】

27．一个有向无环图的拓扑排序序列（ ）是唯一的。【北京邮电大学 2001 一、3 （2分）】

A．一定 B．不一定

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

A．G中有弧 B．G中有一条从Vi到Vj的路径 C．G中没有弧 D．G中有一条从Vj到Vi的路径

【南京理工大学 2000 一、9 （1.5分）】

29. 在用邻接表表示图时，拓扑排序算法时间复杂度为( )。

A. O(n) B. O(n＋e) C. O(n*n) D. O(n*n*n) 【合肥工业大学 2000 一、2 （2分）】【南京理工大学 2001 一、9 （1.5分）】 【青岛大学 2002 二、3 （2分）】 30. 关键路径是事件结点网络中（ ）。【西安电子科技大学 2001应用 一、4 （2分）】

A．从源点到汇点的最长路径 B．从源点到汇点的最短路径 C．最长回路 D．最短回路 31. 下面关于求关键路径的说法不正确的是（ ）。【南京理工大学 1998 一、12 （2分）】 A．求关键路径是以拓扑排序为基础的

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

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

D．关键活动一定位于关键路径上

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

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

B．任何一个关键活动提前完成，那么整个工程将会提前完成 C．所有的关键活动提前完成，那么整个工程将会提前完成 D．某些关键活动提前完成，那么整个工程将会提前完成 【北方交通大学 1999 一、7 （3分）】【北京工业大学 1999 一、1 (2分)】

二、判断题

1.树中的结点和图中的顶点就是指数据结构中的数据元素。（ ）【青岛大学 2001 四、1 （1分）】 2．在n个结点的无向图中，若边数大于n-1,则该图必是连通图。（ ）【中科院软件所1997一、4(1分）】

3．对有n个顶点的无向图，其边数e与各顶点度数间满足下列等式e=

?TD(Vi)i?1n。（ ）

【南京航空航天大学 1996 六、4 （1分）】 4. 有e条边的无向图，在邻接表中有e个结点。（ ）【南京理工大学 1998 二、5 （2分）】

5. 有向图中顶点V的度等于其邻接矩阵中第V行中的1的个数。（ ）【合肥工业大学2001二、7(1分）】

6．强连通图的各顶点间均可达。（ ）【北京邮电大学 2000 一、3 （1分）】 7．强连通分量是无向图的极大强连通子图。（ ）【北京邮电大学 2002 一、7 （1分）】 8．连通分量指的是有向图中的极大连通子图。（ ）【燕山大学 1998 二、4 （2分）】 9．邻接多重表是无向图和有向图的链式存储结构。（ ）【南京航空航天大学 1995 五、5 （1分）】

10. 十字链表是无向图的一种存储结构。（ ）【青岛大学 2001 四、7 （1分）】 11. 无向图的邻接矩阵可用一维数组存储。（ ）【青岛大学 2000 四、5 （1分）】 12．用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。（ ）

【东南大学 2001 一、4 （1分）】 【中山大学 1994 一、3 （2分）】 13．有n个顶点的无向图, 采用邻接矩阵表示, 图中的边数等于邻接矩阵中非零元素之和的

一半。（ ）

【北京邮电大学 1998 一、5 （2分）】 14. 有向图的邻接矩阵是对称的。（ ）【青岛大学 2001 四、6 （1分）】 15．无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。（ ）

【东南大学 2001 一、3 （1分）】【哈尔滨工业大学 1999 三、4】

16. 邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图，而只能使用邻接表存储形式来存储它。（ ）【上海海运学院 1995 一、9（1分） 1997 一、8（1分） 1998 一、9（1分）】

17. 用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中结点个数有关，而与图的边数无关。（ ）【上海海运学院 1996 一、8 （1分） 1999 一、9 （1分）】

18．一个有向图的邻接表和逆邻接表中结点的个数可能不等。（ ）【上海交通大学 1998 一、12】

19．需要借助于一个队列来实现DFS算法。（ ）【南京航空航天大学 1996 六、8 （1分）】 20. 广度遍历生成树描述了从起点到各顶点的最短路径。（ ）【合肥工业大学 2001 二、8 （1分）】

21．任何无向图都存在生成树。（ ）【北京邮电大学 2000 一、1 （1分）】 22. 不同的求最小生成树的方法最后得到的生成树是相同的.（ ）【南京理工大学 1998 二、3 （2分）】

23．带权无向图的最小生成树必是唯一的。（ ）【南京航空航天大学 1996 六、7 （1分）】 24. 最小代价生成树是唯一的。（ ）【山东大学 2001 一、5 （1分）】 25．一个网（带权图）都有唯一的最小生成树。（ ）【大连海事大学 2001 一、14 （1分）】

26．连通图上各边权值均不相同，则该图的最小生成树是唯一的。（ ）【哈尔滨工业大学 1999 三、3】

27．带权的连通无向图的最小（代价）生成树（支撑树）是唯一的。（ ）【中山大学 1994 一、10（2分）】

28. 最小生成树的KRUSKAL算法是一种贪心法（GREEDY）。（ ）【华南理工大学 2002 一、6（1分）】

29. 求最小生成树的普里姆(Prim)算法中边上的权可正可负。（ ）【南京理工大学 1998 二、2 （2分）】

30．带权的连通无向图的最小代价生成树是唯一的。（ ）【东南大学 2001 一、5（1分）】 31. 最小生成树问题是构造连通网的最小代价生成树。（ ）【青岛大学 2001 四、10（1分）】

32. 在图G的最小生成树G1中，可能会有某条边的权值超过未选边的权值。（ ）

【合肥工业大学 2000 二、7（1分）】

k-1

33. 在用Floyd 算法求解各顶点的最短路径时，每个表示两点间路径的path[I,J]一定是

k

path [I,J]的子集(k=1,2,3,?,n)。（ ）【合肥工业大学 2000 二、6 （1分）】 34．拓扑排序算法把一个无向图中的顶点排成一个有序序列。（ ）【南京航空航天大学1995五、8（1分）】

35．拓扑排序算法仅能适用于有向无环图。（ ）【南京航空航天大学 1997 一、7 （1分）】 36. 无环有向图才能进行拓扑排序。（ ）【青岛大学 2002 一、7 （1分）2001 一、8 （1分）】

37. 有环图也能进行拓扑排序。（ ）【青岛大学 2000 四、6 （1分）】

38．拓扑排序的有向图中，最多存在一条环路。（ ）【大连海事大学 2001 一、6（1分）】 39．任何有向图的结点都可以排成拓扑排序，而且拓扑序列不唯一。（ ）【上海交通大学1998 一、13】

40. 既使有向无环图的拓扑序列唯一，也不能唯一确定该图。（ ）【合肥工业大学 2001 二、6（1分）】

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

【中科院软件所 1997 一、5 （1分）】 42．AOV网的含义是以边表示活动的网。（ ）【南京航空航天大学 1995 五、7 （1分）】 43．对一个AOV网，从源点到终点的路径最长的路径称作关键路径。【南京航空航天大学1995五、9(1分）】

44. 关键路径是AOE网中从源点到终点的最长路径。（ ）【青岛大学 2000 四、10（1分）】 45. AOE网一定是有向无环图。（ ）【青岛大学 2001 一、9 （1分）】 46. 在表示某工程的AOE网中，加速其关键路径上的任意关键活动均可缩短整个工程的完成时间。（ ）

【长沙铁道学院 1997 一、2 (1分)】

47．在AOE图中，关键路径上某个活动的时间缩短，整个工程的时间也就必定缩短。（ ）

【大连海事大学 2001 一、15 （1分）】

48．在AOE图中，关键路径上活动的时间延长多少，整个工程的时间也就随之延长多少。（ ）

【大连海事大学 2001 一、16 （1分）】

49．当改变网上某一关键路径上任一关键活动后，必将产生不同的关键路径。【上海交通大学1998 一、14】

三、填空题

1.判断一个无向图是一棵树的条件是______。 2．有向图G的强连通分量是指______。【北京科技大学 1997 一、7】 3．一个连通图的______是一个极小连通子图。【重庆大学 2000 一、1】 4．具有10个顶点的无向图，边的总数最多为______。【华中理工大学 2000 一、7 （1分）】 5．若用n表示图中顶点数目，则有_______条边的无向图成为完全图。【燕山大学1998 一、

6（1分）】

6. 设无向图 G 有n 个顶点和e 条边，每个顶点Vi 的度为di（1<=i<=n〉，则e=______

【福州大学 1998 二、2 (2分)】

7．G是一个非连通无向图，共有28条边，则该图至少有______个顶点。

【西安电子科技大 2001软件一、8 （2分）】

8. 在有n个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要______条弧。

【合肥工业大学 2000 三、8 （2分）】

9．在有n个顶点的有向图中，每个顶点的度最大可达______。【武汉大学 2000 一、3】 10．设G为具有N个顶点的无向连通图，则G中至少有______条边。

【长沙铁道学院 1997 二、2 (2分)】

11．n个顶点的连通无向图，其边的条数至少为______。【哈尔滨工业大学 2000 二、2（1分）】

12．如果含n个顶点的图形形成一个环，则它有______棵生成树。

【西安电子科技大学 2001软件 一、2 （2分）】

13．N个顶点的连通图的生成树含有______条边。【中山大学 1998 一、9 （1分）】 14．构造n个结点的强连通图，至少有______条弧。【北京轻工业学院 2000 一、4（2分）】

15．有N个顶点的有向图，至少需要量______条弧 才能保证是连通的。【西南交通大学 2000 一、3】 16．右图中的强连通分量的个数为（ ）个。

【北京邮电大学 2001 二、5 （2分）】 17．N个顶点的连通图用邻接矩阵表示时,该矩阵 至少有_______个非零元素。【中科院计算所1998一、6（1分）】【中国科技大学1998 一、6（15/6分）】

18．在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的______；对于有向图来说等于该顶点的______。

【燕山大学 2001 二、5 （3分）】

19. 在有向图的邻接矩阵表示中，计算第I个顶点入度的方法是______。【青岛大学 2002 三、7 （2分）】

20. 对于一个具有n个顶点e条边的无向图的邻接表的表示，则表头向量大小为______，邻接表的边结点个数为______。【青岛大学 2002 三、8 （2分）】

21. 遍历图的过程实质上是______，breath-first search遍历图的时间复杂度______；depth-first search遍历图的时间复杂度______，两者不同之处在于______，反映在数据结构上的差别是______。

【厦门大学1999一、3】 22. 已知一无向图G=（V，E），其中V={a,b,c,d,e } E={(a,b),(a,d),(a,c),(d,c),(b,e)}现用某一种图遍历方法从顶点a开始遍历图，得到的序列为abecd，则采用的是______遍历方法。

【南京理工大学 1996 二、2 （2分）】 23. 一无向图G（V，E），其中V（G）={1,2,3,4,5,6,7}，E（G）={（1,2）,(1,3），（2,4），（2,5），（3,6），（3,7），（6,7）（5,1）},对该图从顶点3开始进行遍历，去掉遍历中未走过的边，得一生成树G’(V，E’）,V（G’）=V（G），E（G’）={（1,3），（3,6），（7,3），（1,2），（1,5），（2,4）}，则采用的遍历方法是______。

【南京理工大学 1997 三、6 （1分）】 24. 为了实现图的广度优先搜索，除了一个标志数组标志已访问的图的结点外，还需______存放被访问的结点以实现遍历。【南京理工大学 1999 二、9 （2分）】

25. 按下图所示，画出它的广度优先生成树______和深度优先生成树______。

【西安电子科技大学 1998 三、6 （5分）】

26．构造连通网最小生成树的两个典型算法是______。【北京科技大学 1998 一、5】 27．求图的最小生成树有两种算法，______算法适合于求稀疏图的最小生成树。

【南京理工大学 2001 二、6（2分）】

28. Prim（普里姆）算法适用于求______的网的最小生成树；kruskal（克鲁斯卡尔）算法适用于求______的网的最小生成树。【厦门大学1999 一、4】

29．克鲁斯卡尔算法的时间复杂度为______,它对______图较为适合。【中科院计算所1999二、3（2分）】

30．对于含N个顶点E条边的无向连通图，利用Prim算法生成最小代价生成树其时间复杂度为______，利用Kruskal算法生成最小代价生成树其时间复杂度为______。【长沙铁道学院 1998 二、2 (4分)】

31．下面描述的是一种构造最小生成树算法的基本思想。设要处理的无向图包括n个节点V1，V2，．．．，Vn，用相邻矩阵A表示，边的权全是正数。请在下列划线处填上正确叙述。 （1）．若（Vi，Vj）是边，则A（i，j）的值等于______，若（Vi，Vj）不是边，则A（i，j）的值是一个比任何边的权______， 矩阵的对角线元素全为0。 （2）．构造最小生成树过程中，若节点Vi已包括进生成树，就把相邻矩阵的对角线元素A（i，i）置成______，若（Vi，Vj）已包括进生成树，就把矩阵元素A（i，j）置成______。 （3）．算法结束时，相邻矩阵中_____的元素指出最小生成树的_____。【山东工业大学1998二、4(6分）】

32. 有一个用于n个顶点连通带权无向图的算法描述如下： （1）．设集合T1与T2，初始均为空； （2）．在连通图上任选一点加入T1； （3）．以下步骤重复n-1次：

a.在i属于T1，j不属于T1的边中选最小权的边； b.该边加入T2。

上述算法完成后，T2中共有______条边，该算法称______算法，T2中的边构成图的______。

【南京理工大学 1999 二、7 （4分）】 33. 有向图G可拓扑排序的判别条件是______。【长沙铁道学院 1998 二、9(2分)】

34. Dijkstra最短路径算法从源点到其余各顶点的最短路径的路径长度按______次序依次产生，该算法弧上的权出现______情况时，不能正确产生最短路径。【南京理工大学 1999 二、8（4分）】

35. 求从某源点到其余各顶点的Dijkstra算法在图的顶点数为10，用邻接矩阵表示图时计算时间约为10ms,则在图的顶点数为40，计算时间约为______ms。【南京理工大学 2000 二、3 （1.5分）】 36．求最短路径的Dijkstra算法的时间复杂度为______。【哈尔滨工业大学 2001 一、5 （2分）】

37.有向图G=(V,E),其中 V(G)={0,1,2,3,4,5}，用三元组表示弧及弧上的权d.E(G)为{<0,5,100>,<0,2,10><1,2,5><0,4,30><4,5,60><3,5,10><2,3,50><4,3,20>}，则从源点0到顶点3的最短路径长度是______，经过的中间顶点是______。【南京理工大学 1998 三、6 （4分）】

38. 上面的图去掉有向弧看成无向图则对应的最小生成树的边权之和为______。

【南京理工大学 1998 三、7（4分）】

39．设有向图有n个顶点和e条边，进行拓扑排序时，总的计算时间为______。

【西安电子科技大学 1999软件 一、7 （2分）】【武汉大学 2000 一、7】

40．AOV网中,结点表示______,边表示______。AOE网中,结点表示______,边表示______。

【北京理工大学2001七、3（2分）】

41．在AOE网中，从源点到汇点路径上各活动时间总和最长的路径称为______。【重庆大学2000一、2】

42．在 AOV网 中，存在环意味着______，这是______的；对程序的数据流图来说，它表明存在______。

【厦门大学1999一、2】

43. 当一个AOV网用邻接表表示时，可按下列方法进行拓扑排序。 （1）．查邻接表中入度为______的顶点，并进栈； （2）．若栈不空，则①输出栈顶元素Vj，并退栈；②查Vj的直接后继Vk，对Vk入度处理，处理方法是______； （3）．若栈空时，输出顶点数小于图的顶点数，说明有______，否则拓扑排序完成。 【南京理工大学 1996 二、3 （6分）】 44．已知图的邻接表结构为： CONST vtxnum={图的顶点数} TYPE vtxptr=1..vtxnum; arcptr=^arcnode;

arcnode=RECORD adjvex:vtxptr; nextarc:arcptr END;

vexnode=RECORD vexdata:{和顶点相关的信息}；firstarc:arcptr END;

adjlist=ARRAY[vtxptr]OF vexnode;

本算法是实现图的深度优先遍历的非递归算法。其中，使用一个顺序栈stack。栈顶指针为top。visited为标志数组。

PROC dfs(g:adjlist;v0:vtxptr);

top=0; write(v0); visited[v0]:=ture; p:=g[v0].firstarc; WHILE (top<>0)OR(p<>NIL)DO

[WHILE(1)_______DO [v:=p^.adjvex;

IF(2)_______ THEN p:=p^.nextarc

ELSE [write(v); visited[v]:=true; top:=top+1; stack[top]:=p;

(3)_______] ]

IF top<>0 THEN[p:=stack[top]; top:=top-1; (4)_______] ]

ENDP.同济大学 2000 二、2 (10分)】

45．下面的算法完成图的深度优先遍历，请填空。

PROGRAM graph_traver; CONST nl=max_node_number;

TYPE vtxptr=1..nl; vtxptr0=0..nl; arcptr=^arcnode;

arcnode=RECORD vexi ,vexj: vtxptr; nexti, nextj: arcptr; END;;

vexnode=RECORD vexdata: char; firstin，firstout: arcptr; END; graph=ARRAY[vtxptr0] OF vexnode ; VAR ga:graph; n: integer;

visited: ARRAY[vtxptr0] OF boolean ; FUNC order (g: graph; v: char): vtxptr; (1)_______; i:=n;

WHILE g[i].vexdata<>v DO i:=i-1; order:=i; ENDF；

PROC creat(var g: graph); readln(n,e);

FOR i:= 1 TO n DO [readln(g[i].vexdata); g[i].firstin :=NIL ; g[i].firstout:=NIL;]

FOR k:= 1 TO e DO [readln (vt,vh);

i:=order (g,vt); j:=order (g,vh); new (p); p^.vexi:=i ; p^.vexj:=j

p^.nextj:= ____(2)____; ___(3)____ :=p; p^.nexti:=: ____(4)____; ___(5)____ :=p;]

ENDP;

FUNC firstadj(g:graph; v:char): vtxptr0; i:=order(g,v); p:=g[i].firstout;

IF p<>NIL THEN firstadj:=(6)_______ELSE firstadj:=0; ENDF;

FUNC nextadj(g:graph; v:char; w:char): vtxptr0; i:=order(g,v); j:=order(g,w); p:=(7)_______; WHILE(p<>NIL ) AND (p^.vexj<>j) DO(8)______;

IF (9)______AND(10)______THEN nextadj:=p^.nexti^.vexj ELSE nextadj:=0; ENDF;

PROC dfs(g:graph; v0:char);

write(v0:2); visited[order(g,v0)]:=true; w:=(11)_______; WHILE w<>0 DO

[IF (12)______ THEN dfs(g,g[w].vexdata); w:=(13)_______;] ENDP;

PROC traver(g:graph);

FOR i:=1 TO n DO visited[i]:=false;

FOR i:=1 TO n DO IF NOT visited[i] THEN dfs(g,g[i].vexdata); ENDP; BEGIN

creat(ga); traver(ga);

END. 【北方交通大学 1999 三（20分）】

46．n个顶点的有向图用邻接矩阵array表示，下面是其拓扑排序算法，试补充完整。 注：（1）．图的顶点号从 0开始计； （2）．indegree 是有n个分量的一维数组，放顶点的入度；

（3）．函数 crein 用于算顶点入度； （4）．有三个函数push(data),pop( ),check( )其含义为数据 data进栈，退栈和测试栈是否空（不空返回1，否则0）。

crein( array ,indegree,n)

{ for (i=0;i

for(i=0,i

for (j=0;j

topsort (array,indegree,n)

{ count= ((4)_______)

for (i=0;i

while (check( ))

{ vex=pop( ); printf(vex); count++; for (i=0;i

if ((7)_______ ) { indegree[i]--; if ((8)_______ ) push(i); } } } if( count

47．假设给定的有向图是用邻接表表示，作为输入的是图中顶点个数n和边的个数m, 以及图的m条边。在下面的程序中，我们用readdata程序过程输入图的信息，并建立该图的邻接表；利用topol程序过程获得图中顶点的一个拓扑序列。

PROGRAM topol_order(input , output) ; CONST maxn=20 ;

TYPE nodeptr=^nltype ;

nltype=RECORD num : integer ; link : nodeptr END ; chtype=RECORD count : integer ; head : nodeptr END ;

VAR ch : ARRAY [1 .. maxn] OF chtype ; m , n , top : integer ; PROCEDURE readdata ;

VAR i , j , u , v : integer ; p : nodeptr ; BEGIN

write (′input vertex number n= ′); readln (n) ; write (′input edge number m= ′); readln(m) ;

FOR i:=1 TO n DO BEGIN ch[i].count:= 0; ch[i].head:=NIL END; writeln(′input edges :′); FOR j:= 1 TO m DO

BEGIN write( j :3 , ′: ′) ; readln( u , v ) ; new( p ) ;

ch[v].count:=ch[v].count+1; p^.num:=v; (1) ___ ; (2) __; END END ;

PROCEDURE topol ;

VAR i, j, k: integer; t: nodeptr ; BEGIN top:= 0 ;

FOR i := 1 TO n DO

IF ch[i].count=0 THEN BEGIN ch[i].count := top ;top := i END; i:= 0 ;

WHILE (3) ___ DO

BEGIN (4) __; (5) __ ; write(j : 5) ;i:= i + 1 ;t:=ch[j].head ; WHILE t<>NIL DO

BEGIN k := t^.num ; ch[k].count:=ch[k].count–1 ;

IF ch[k].count=0 THEN BEGIN ch[k].count:=top; top:=k END;

(6) ______ ; END

END ; writeln;

IF i

readdata ; writeln (′output topol order : ′); topol END. 【复旦大学 1995 三 （18分）】 48．如下为拓扑排序的C程序，

V2 （1）．列出对右图执行该程序后的输出结果。

（2）．在程序空白处填上适当语句。 V1 V3 V5 void topsort(hdnodes graph [],int n) V4 V6 {int i,j,k,top; node_pointer ptr ;

top=-1;

for (i=0; i

if (!graph[i].count){graph[i].count=top; top=i; } for (i=0; i

if(1)____ {fprintf(stderr, \ else {j=top;(2)_____; printf( \

for (ptr=graph[j].link; ptr; ptr=ptr->link) {k=ptr->vertex; graph[k].count--;

if((3)_____) {graph[k].count=top; top=k; } } } } 【浙江大学 2000 六(15分)】

四、 应用题 1．（1）．如果G1是一个具有n个顶点的连通无向图，那么G1最多有多少条边？G1最少有多少条边？ （2）．如果G2是一个具有n个顶点的强连通有向图，那么G2最多有多少条边？G2最少有多少条边？ （3）．如果G3是一个具有n个顶点的弱连通有向图，那么G3最多有多少条边？G3最少有多少条边？

【复旦大学 1997 一（9分）】

2．n个顶点的无向连通图最少有多少条边？n个顶点的有向连通图最少有多少条边？

【山东大学 2000 一、3 (4分)】

3．一个二部图的邻接矩阵A是一个什么类型的矩阵？【北京科技大学 1999 一、8（2分）】 4．证明：具有n个顶点和多于n-1条边的无向连通图G一定不是树。【东南大学 1993 四（10分）】

5．证明对有向图的顶点适当的编号，可使其邻接矩阵为下三角形且主对角线为全0的充要条件是该图为无环图。【北京邮电大学 2002 三 （10分）】

6．用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边的条数是否有关？

【西安电子科技大学 2000计应用 一、6（5分）】 7．请回答下列关于图(Graph)的一些问题：（每题4分） （1）．有n个顶点的有向强连通图最多有多少条边?最少有多少条边? （2）．表示有1000个顶点、l000条边的有向图的邻接矩阵有多少个矩阵元素？是否稀

疏矩阵？

（3）．对于一个有向图，不用拓扑排序，如何判断图中是否存在环？【清华大学2000一(12分）】

8．解答问题。设有数据逻辑结构为： B = (K, R), K = {k1, k2, ?, k9}

R={, , ,, , ,, , , , } （1）．画出这个逻辑结构的图示。（3分） （2）．相对于关系r, 指出所有的开始接点和终端结点。（2分） （3）．分别对关系r中的开始结点，举出一个拓扑序列的例子。（4分） （4）．分别画出该逻辑结构的正向邻接表和逆向邻接表。（6分）【山东工业大学 1999 三 （15分）】

9．有向图的邻接表存储如下：（1）．画出其邻接矩阵存储；（2）．写出图的所有强连通分量；（3）．写出顶点a到顶点i的全部简单路径。【东北大学 1997 一、5 (5分)】

10．试用下列三种表示法画出网G 的存储结构，并评述这三种表示法的优、缺点： （1）．邻接矩阵表示法; （2）．邻接表表示法; （3）．其它表示法。【华中理工大学2000 三（12分）】

11．已知无向图G，V（G）={1，2，3，4}，E（G）={（1，2），（1，3），（2，3），（2，4），（3，4）}试画出G的邻接多表，并说明，若已知点I，如何根据邻接多表找到与I相邻的点j？

【东南大学 1994 一、2 （8分） 1998 一、6（8分）】 12．如何对有向图中的顶点号重新安排可使得该图的邻接矩阵中所有的1都集中到对角线以上？

【清华大学 1999 一、5 （2分）】

13．假定Ｇ＝（V，E）是有向图，V＝｛1,2，．．．,N｝，N＞＝1，G以邻接矩阵方式存储，G的邻接矩阵为A，即Ａ是一个二维数组，如果i到j有边，则A[i,j]=1，否则A[i,j]=0，请给出一个算法，该算法能判断G是否是非循环图（即G中是否存在回路），要求算法的时间复杂性为O(n*n)。

【吉林大学 1998 三(16分)】

14． 首先将如下图所示的无向图给出其存储结构的邻接链表表示，然后写出对其分别进行深度，广度优先遍历的结果。 【天津大学 1999 一】 15．下面的邻接表表示一个给定的无向图

（1）给出从顶点v1开始,对图G用深度优先搜索法进行遍历时的顶点序列； （2）给出从顶点v1开始,对图G用广度优先搜索法进行遍历时的顶点序列。【复旦大学1998六(10分))

1 2 5

1 3 4 8 6 7 8 9 10

15题图 14题图 16题图

16．给出图G：

（1）．画出G的邻接表表示图； （2）．根据你画出的邻接表，以顶点①为根，画出G的深度优先生成树和广度优先生成树。 【南开大学 1997 五 (14分)】

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

234?1

5?1342

124? 31235? 4 524?

【北京轻工业学院 1998 八 （6分）】 18．对一个图进行遍历可以得到不同的遍历序列，那么导致得到的遍历序列不唯一的因素有哪些？

【北京航空航天大学 1998 一、7 （4分）】 19．解答下面的问题 （1）．如果每个指针需要4个字节，每个顶点的标号占2个字节，每条边的权值占2个字节。下图采用哪种表示法所需的空间较多？为什么? 2 9 8 7 10 5

1 20 4 1 10 5 6

10 2 2 3 3 6 11 4 3 15 3 5

19题图 20题图

（2）．写出下图从顶点1开始的DFS树。【西安电子科技大学 2000计应用 六 （10分）】 20．如下所示的连通图，请画出： （1）．以顶点①为根的深度优先生成树；（5分） （2）．如果有关节点，请找出所有的关节点。（5分）【清华大学 1998 七 （10分）】 21．某田径赛中各选手的参赛项目表如下: 姓名 参 赛 项 9 ZHAO A B E QIAN C D SHUN C E F LI D F A ZHOU B F 设项目A ,B ,?，F各表示一数据元素,若两项目不能同时举行,则将其连线(约束条件). 3 4 5 6 7 2 （1）．根据此表及约束条件画出相应的图状结构模型,并画出此图的邻接表结构; （2）．写出从元素A出发按“广度优先搜索”算法遍历此图的元素序列.

【北京科技大学 1999 五 2000 五 （12分）】 22．已知无向图如下所示： （1）．给出从V1开始的广度优先搜索序列；（2）．画出它的邻接表； （3）．画出从V1开始深度优先搜索生成树。【燕山大学 2000 五 （5分）】 234?v1

5?1v2

5?1v3

v416?

v523? v64?

第22题图 第23题图 23．已知某图的邻接表为

（1）．写出此邻接表对应的邻接矩阵；（2分） （2）．写出由v1开始的深度优先遍历的序列；（2分） （3）．写出由v1开始的深度优先的生成树；（2分） （4）．写出由v1开始的广度优先遍历的序列；（2分） （5）．写出由v1开始的广度优先的生成树；（2分） （6）．写出将无向图的邻接表转换成邻接矩阵的算法。（8分） 【山东大学 1998 六、

A 2 18分】

5 D 6 4 C 24．考虑右图： B E 1 (1)从顶点A出发，求它的深度优先生成树

3 5 3

1 (2)从顶点E出发，求它的广度优先生成树 G F

（3）根据普利姆(Prim) 算法， 求它的最小生成树【上海交通大学 1999 六 (12分)】

25.在什么情况下，Prim算法与Kruskual算法生成不同的MST？

【西安电子科技大学 2000计应用 一、11 （5分）】 26．下面是求无向连通图最小生成树的一种方法。

将图中所有边按权重从大到小排序为（e1,e2,?,em）

i:=1

WHILE (所剩边数 >=顶点数)

BEGIN

从图中删去ei

若图不再连通，则恢复ei i:=i+1 END.

试证明这个算法所得的图是原图的最小代价生成树。【北京邮电大学 1999 五 （10分）】 27．已知一个无向图如下图所示，要求分别用Prim和Kruskal算法生成最小树（假设以①为起点，试画出构造过程）。【哈尔滨工业大学 1999 九 （8分）】 20 1 4 1 9 4 2 5 11 7 8 2 9 6 6 14 6 3 10 10 5 3 2 6 5 4 4 5 18

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

（1）．请回答什么是G的最小生成树； （2）．G为下图所示,请找出G的所有最小生成树。【北方交通大学 1993 二 （12分）】 29．试写出用克鲁斯卡尔（Kruskal）算法构造下图的一棵最小支撑（或生成）树的过程。

5

21 7818 21 2 5 6 12 83 23 85 3 8 7 4 6415 3325 10 7 24 6 7420 3

4765第29图 6【吉林大学 2000 一、3 (3分)】 30.求出下图的最小生成树。【合肥工业大学 1999 四、2 （5分）】 第30题图

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

【浙江大学1994五(8分)】 第32题图 32．请看下边的无向加权图。 （1）．写出它的邻接矩阵（ 5分） （2）．按Prim算法求其最小生成树，并给出构造最小生成树过程中辅助数组的各分量值（15分）

辅助数组内各分量值：【华北计算机系统工程研究所 1999 四（20分）】 Y Closedge Vex Lowcost 2 3 4 5 6 7 8 U V.-U Vex Lowcost Vex Lowcost Vex Lowcost Vex Lowcost Vex Lowcost Vex Lowcost Vex Lowcost 33．已知世界六大城市为:北京(Pe)、纽约(N)、巴黎(Pa)、 伦敦(L) 、 东京(T) 、 墨西哥(M),下表给定了这六大城市之间的交通里程:

世界六大城市交通里程表(单位:百公里)

PE N PA L T M PE N PA L T M 1 2 5 1 3 8 1 4 3 2 4 6 2 3 2 3 4 4 3 5 1 3 6 10 4 5 7 4 6 11 5 6 15 109 82 81 21 124 109 58 55 108 32 82 58 3 97 92 81 55 3 95 89 21 108 97 95 113 124 32 92 89 113 （1）．画出这六大城市的交通网络图; （2）．画出该图的邻接表表示法; （3）．画出该图按权值递增的顺序来构造的最小(代价)生成树. 【上海海运学院1995 六（9分） 1999 五 （14分）】 34．已知顶点1-6和输入边与权值的序列（如右图所示）：每行三个数表示一条边

的两个端点和其权值，共11行。请你： （1）．采用邻接多重表表示该无向网，用类PASCAL语言描述该数据结构，画出存

储结构示意图，要求符合在边结点链表头部插入的算法和输入序列的次序。 （2）．分别写出从顶点1出发的深度优先和广度优先遍历顶点序列，以及相应的

生成树。 （3）．按prim算法列表计算，从顶点1始求最小生成树，并图示该树。 【北京工业大学 1999 四(20分)】

35．下图表示一个地区的通讯网，边表示城市间的通讯线路，边上的权表示架设线路花费的代价，如何选择能沟通每个城市且总代价最省的n-1条线路，画出所有可能的选择。【东北大学2000一、4(4分)】

16 21 2153 d 8 1 b 5 11 195 c 4 e a 43614 6 7 h 3 2 f 633 5618 第36题图

36．设无向网G 如上： 第35题图 （1）． 设顶点a、b、c、d、e、f、h的序号分别为1、2、3、4、5、6、7，请列出网G的邻接矩阵、画出网G 的邻接表结构: （2）．写出从顶点a出发,按“深度优先搜索”和“广度优先搜索”方法遍历网G所的到的顶点序列：

按Prim算法求出网G的一棵最小生成树。【北京科技大学 2001 五(12分)】

12

37．有一图的邻接矩阵如下，试给出用弗洛伊德算法求各点间最短距离的矩阵序列A，A，34

A，A。

?02?????016????5?04???3??0? A=?【北京邮电大学2001四、5(5分）】

38．下图所示是一带权有向图的邻接表法存储表示。其中出边表中的每个结点均含有三个字段，依次为边的另一个顶点在顶点表中的序号、边上的权值和指向下一个边结点的指针。试求：

（1）．该带权有向图的图形； （2）．从顶点V1为起点的广度优先周游的顶点序列及对应的生成树（即支撑树）； （3）．以顶点V1为起点的深度优先周游生成树； （4）．由顶点V1到顶点V3的最短路径。【中山大学 1994 四 （12分）】

(顶点边)（出边表）b 6 e 5 h 2 1V1233429625?3 2 5 4 9 8 a 2 c 4 f 2 i 9 z

2V2336?2 1 6 4 1 4 3 d g 9 j 2 3V3? 第39 题图

V44303842?235

1018?16V5 5 6V6?

39．用最短路径算法，求如下图中a到z的最短通路。【西南财经大学 1999 四】

40．已知一有向网的邻接矩阵如下，如需在其中一个结点建立娱乐中心，要求该结点距其它各结点的最长往返路程最短，相同条件下总的往返路程越短越好，问娱乐中心应选址何处？给出解题过程。

V1?02???3?V2??032?????V3?4?0?4????V4?1??01??V5??1??03???V6???25?0?

第41题图

【北京邮电大学 2002 四、1 （10分）】

41．求出下图中顶点1到其余各顶点的最短路径。【厦门大学 2002 八、2 （5分）】 42．试利用Dijkstra算法求下图中从顶点a到其他个顶点间的最短路径，写出执行算法过程中各步的状态。

【东南大学 2000 四（10分）】

43．对于如下的加权有向图，给出算法Dijkstra产生的最短路径的支撑树，设顶点A为源

点，并写出生成过程。【吉林大学 1999 一、2 (4分)】

15

第43题图

第42题图

44．已知图的邻接矩阵为： V1 V2 V3 V4 V5 V6 V7 V8 V9 V10 45A3B40E2120 2015CD353020

V1 0 1 1 1 0 0 0 0 0 0 V2 0 0 0 1 1 0 0 0 0 0 V3 0 0 0 1 0 1 0 0 0 0 V4 0 0 0 0 0 1 1 0 1 0 V5 0 0 0 0 0 0 1 0 0 0 V6 0 0 0 0 0 0 0 1 1 0 V7 0 0 0 0 0 0 0 0 1 0 V8 0 0 0 0 0 0 0 0 0 1 V9 0 0 0 0 0 0 0 0 0 1 V10 0 0 0 0 0 0 0 0 0 0 当用邻接表作为图的存储结构，且邻接表都按序号从大到小排序时，试写出： （1）．以顶点V1为出发点的唯一的深度优先遍历； （2）．以顶点V1为出发点的唯一的广度优先遍历； （3）．该图唯一的拓扑有序序列。【同济大学 1998 一 (12分 )】 45．已知一图如下图所示：

（1）．写出该图的邻接矩阵； （2）．写出全部拓扑排序； （3）．以v1为源点,以v8为终点，给出所有事件允许发生的最早时间和最晚时间，并

46．（1）．对于有向无环图，叙述求拓扑有序序列的步骤； （2）．对于以下的图，写出它的四个不同的拓扑有序序列。【南开大学 1998 二 (12分)】 47．有向图的拓扑排序能否用图的深度搜索模式来查找?若能，请简述方法，若不能，请简述原因

【西北大学2000二、8(5分)】

48．下图是带权的有向图G的邻接表表示法，求：

（1）．以结点V1出发深度遍历图G所得的结点序列； （2）．以结点V1出发广度遍历图G所得的结点序列； （3）．从结点V1到结点V8的最短路径； （4）．从结点V1到结点V8的关键路径。

给出关键路径； （4）．求V1结点到各点的最短距离。【北京邮电大学 2000 五 （15分）】

2 3 3 V1 V3 V5 V7 10 1 7 3 2 1 4 8 2

3 6 5 6 4 V8 V6 V4 V2 5

第46题图 第45题图

【青岛海洋大学 1999 四（10分）】

49．对有五个结点{ A,B, C, D, E}的图的邻接矩阵，

?010030?10???0????????60020?????10?0????????500??

（1）．画出逻辑图 ； （2）．画出图的十字链表存储； （3）．基于邻接矩阵写出图的深度、广度优先遍历序列； （4）．计算图的关键路径。

【华南师范大学1999三(20分)】

50．何为AOE网的始点和终点，一个正常的AOE网是否只有一个始点和一个终点？

【首都经贸大学 1997 一、4 （4分）】

51．下表给出了某工程各工序之间的优先关系和各工序所需时间

（1）．画出相应的AOE网 （2）．列出各事件的最早发生时间,最迟发生时间 （3）．找出关键路径并指明完成该工程所需最短时间. 【武汉交通科技大学 1996 二、6 (7分)】

工序 A B C E F G H I J K L 代号 D M N 所需 10 50 15 300 15 120 15 30 时间 15 8 40 60 20 40 先驱 -- A,B C,D B E G,I E I F,I H,J,K L G 工作 -- B 52．对图示的AOE网络，计算各活动弧的e(ai)和l(ai)的函数值，各事件（顶点）的ve（Vj）和vl (Vj)的函数值，列出各条关键路径。【北京轻工业学院 1997 四 （15分）】

A1B?6534C 11106F916H1221 17W72E8G133 2 1 0 2 2 5 4 3 3 7 5 4 3 8

D

6 4 4 9 3 7 10 11 1 6 5 2 7 第52题图 第53题 工程作业的网络图 53．请写出应填入下列叙述中（ ）内的正确答案。

某一工程作业的网络图如图所示，其中箭头表示作业，箭头边的数字表示完成作业所需的天数。箭头前后的圆圈表示事件，圆圈中的数字表示事件的编号。用事件编号的序列（例如0-2-7-9-11）表示进行作业的路径。

完成此工程的关键路径是（A）完成此工程所需的最少天数为（B）天，此工程中具有最大充裕天数的事件是（C），充裕天数是（D）。关键路径上的事件的充裕天数是（E）。【上海大学 2002 三 （10分）】

五、算法设计题 1．（单独命题考生做）设无向图G有n个顶点，m条边。试编写用邻接表存储该图的算法。（设顶点值用1～n或0～n-1编号） 【南京航空航天大学 1996 十二 （10分）】

2．请用流程图或类高级语言(pascal或c)表示算法。已知有向图有n个顶点,请写算法,根据用户输入的偶对建立该有向图的邻接表。即接受用户输入的(以其中之一为0标志结束),对于每条这样的边,申请一个结点,并插入到的单链表中,如此反复,直到将图中所有边处理完毕。提示：先产生邻接表的n个头结点（其结点数值域从1到n）。【上海大学 2000 四 （16分）】

3．设无向图G有n个点e条边，写一算法建立G的邻接多表，要求该算法时间复杂性为O（n+e），且除邻接多表本身所占空间之外只用O（1）辅助空间。【东南大学 1995 六（16分） 1997 二 （15分）】

4．给出以十字链表作存储结构，建立图的算法，输入(i,j,v)其中i,j为顶点号，v为权值。

【河海大学 1998 六 （10分）】

5．设有向G图有n个点(用1,2,?,n表示),e条边,写一算法根据其邻接表生成其反向邻接表,要求算法复杂性为O(n+e)。【东南大学 1996 三 （13分）】 类似本题的另外叙述有：

（1）下图（编者略）是有向图按出度建立的邻接表，试写一算法，将此出度邻接表改成入度建立的邻接表。【北京邮电大学 1993 五 （15分）】

（2）编写算法实现以下功能：根据含有n个顶点的有向图邻接表，构造相应的逆邻接表。

【东南大学 1992 六（18分）】

6．写出从图的邻接表表示转换成邻接矩阵表示的算法，用类PASCAL语言（或C语言）写成过程形式。

【南开大学 1998 四 (16分)】 类似本题的另外叙述有：

（1）已知某个图的邻接表，试建立该图的相邻矩阵。【天津大学 1999 五】 7．设已给出图的邻接矩阵，要求将邻接矩阵转换为邻接表，用类pascal语言写为过程形式。

【南开大学1998四( 14分)】 类似本题的另外叙述有：

（1）设已给出图的邻接矩阵，要求将图的邻接矩阵转化为邻接表，试实现其算法。【南开大学2000三3】

（2）编写算法，将图的邻接矩阵存储改为邻接表的存储。【中山大学 1998 五、2 （10分）】

8．试写一算法，判断以邻接表方式存储的有向图中是否存在由顶点Vi到顶点Vj的路径（i<>j）。注意：算法中涉及的图的基本操作必须在存储结构上实现。【哈尔滨工业大学 2001 九 （12分）】

类似本题的另外叙述有：

（1）设计一个深度优先搜索算法，以判断用邻接表方式存储的有向图中是否存在由顶点Vi到顶点Vj（i≠j）的路径。【中山大学 1999数 四 （15分）】

（2）按图的宽度优先搜索法写一算法判别以邻接矩阵存储的有向图中是否存在由顶点Vi到顶点Vj的路径（i≠j）。【中山大学 1997 五 （10分）】 （3）请用流程图或类高级语言(pascal或c)表示算法。写算法判别以邻接方式存储的无向图中是否存在由顶点Vi到顶点Vj的路径(i≠j)。【上海大学 1999 三、2 （14分）】 9．已知无向图采用邻接表存储方式，试写出删除边（i，j）的算法。 【东南大学 1999 三 （10分）】

类似本题的另外叙述有：

（1）一个无向连通图的存储结构以邻接表的形式给定，设计算法删除该图中的一条边(i,j)。

【北京工业大学 1996 二 (15分)】

（2）无向图G已按下图（编者略）邻接表存储。试编写算法在该邻接表上操作，删除从顶点I到顶点J之间的一条边。【上海大学 1996 六（18分）】

（3）设无向图G用邻接表表示，（编者略）请写出在该无向图中删除边 (i,j)的算法。 【青岛海洋大学 1999 五（13分）】 10．假设有向图以邻接表存储，试编写算法删除弧的算法。【北京轻工业学院 1997 五（10分）】 11．假设有向图以十字链表存储，试编写算法，插入弧。【北京轻工业学院 1998 四 （14分）】

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

【南京理工大学 1997 四、2（10分）】 13．假设以邻接矩阵作为图的存储结构，编写算法判别在给定的有向图中是否存在一个简单有向回路，若存在，则以顶点序列的方式输出该回路（找到一条即可）。（注：图中不存在顶点到自己的弧）

【清华大学 1994 六 （15分）】 类似本题的另外叙述有：

（1）假定G=（V，E）是有向图，V={1，2，?，n }，n>=1，G以邻接矩阵方式存储，G的邻接矩阵为A，即A是一个二维数组，如果i到 j有边，则A[ i,j]=1，否则A[ i,j]=0。请给出一个算法，该算法能判断G是否是非循环图（即G中是否存在回路），要求算法的时间复杂性为O（ n*n ）。

【吉林大学1997五(16分)】 14．假设一个有向图G已经以十字链表形式存储在内存中，试写一个判断该有向图中是否有环路（回路）的算法。【东北大学 2000 四、3 (12分)】

15．用邻接多重表存储结构，编写FIRST-ADJ(G,V)函数，函数返回值为第一个邻接点，若V没有邻接点，返回零。【北京工商大学 1999 四 （12分）】

16．在有向图G中，如果r到G中的每个结点都有路径可达，则称结点r为G的根结点。编写一个算法完成下列功能： （1）．建立有向图G的邻接表存储结构； （2）．判断有向图G是否有根，若有，则打印出所有根结点的值。【东北大学 2001 五 (15分)】

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

【南京航空航天大学 1995 十一（10分）】

类似本题的另外叙述有： （1）写出求无向图G中各连通分量的顶点集的算法COMF（G）。可调用的运算是：FIRST_ADJ（G，V）--求顶点V的第一邻接点，NEXTADJ（G，V，W）--求顶点V关于W的下一个邻接点。 【北京科技大学 1998 八、2（10分）】

（2）编程求解无向图G的所有连通分量。 【南京航空航天大学 2000 七】 18．设无向图G已用邻接表结构存储，顶点表为GL[n] (n为图中顶点数)，试用“广度优先搜索”方法，写出求图G中各连通分量的C语言描述算法：BFSCOM(GL)。（注：算法中可调用队列操作的基本算法。）

【北京科技大学 2001 七、2 （10分）】

19．设一个连通无向图G=(V,E)采用邻接表方式存储，V=(1,2,?,n}，一维数组HAED[1?n]用来存放每个单链表的头指针，单链表中节点结构为(VER,LINK)，其中LINK是链接字段，VER字段表示顶点内容，一维数组MARK[1?n]用于对相应顶点加标号，MARK[i]=0表示顶点i未被访问到, MARK[i]=1表示顶点i已经被访问过,试写出对上述图G进行广度(或宽度)优先遍历(或访问)的非递归算法BFS(HEAD,n,s,MARK,MARK)，其中S为任一遍历起始顶点。

【吉林大学2000二、1（7分）】

20．写出图的深度优先搜索DFS算法的非递归算法。 【北京邮电大学 1994 十 （15分）】 21．已知连通图如下： D F C A B

E （1）．给出本图的邻接表； （2）．若从顶点B出发对该图进行遍历，在（1）的基础上分别给出本图的按深度优先搜索和按广度优先搜索的顶点序列； （3）．写出按深度优先搜索的递归程序。【厦门大学 2001 三 （12%分）】 22．试编写从某一顶点出发按深度优先搜索策略在图的邻接表上遍历一个强连通图的非递归算法。（用类PASCAL语言）【燕山大学 1999 十、2 （8分）】 23. 设计算法以实现对无向图G的深度遍历，要求：将每一个连通分量中的顶点以一个表的形式输出。例如，下图的输出结果为：（1，3）（2，6，7，4，5，8）（9，10）

1 2 4 5 9

3 8 10 6 7

（注：本算法中可以调用以下几个函数： firstadj（g,v）——返回图g中顶点v的第一个邻接点的号码，若不存在，则返回0；

nextadj（g,v,w）——返回图g中顶点v的邻接点中处于w之后的邻接点的号码，若不存在，则返回0。nodes（g）——返回图g中的顶点数） 【合肥工业大学 2000 五、4（8分）】

24．请设计一个图的抽象数据类型（只需要用类PASCAL或类C/C++语言给出其主要功能函数或过程的接口说明，不需要指定存储结构，也不需要写出函数或过程的实现方法），利用抽象数据类型所提供的函数或过程编写图的宽度优先周游算法。算法不应该涉及具体的存储结构，也不允许不通过函数或过程而直接引用图结构的数据成员，抽象数据类型和算法都应该加足够的注释。【北京大学 1999 二、1（10分）】

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

【合肥工业大学 1999 五、5 (8分)】

26．已有邻接表表示的有向图，请编程判断从第u顶点至第v顶点是否有简单路径，若有则印出该路径上的顶点。要求：先描述图的存储结构，并简述算法思路；查找邻接点等图的运算要自己实现。（尽量采用非递归算法，否则满分１５分）【北京工业大学 2000 六 （20分）】

类似本题的另外叙述有： (1) 已知有向图和图中的两个结点u和v，试编写算法求有向图中从u到v的所有简单

路径。

【东南大学 2001 四 （15分）】

(2) 已知有向图和图中两个顶点U和V，编写算法求有向图中从U到V的所有简单路径，并以下图为例执行所编写的算法，画出相应的搜索过程图。【山东科技大学 2002 六 （18分）】

a u b f C e 第27题图

v d 第26题图

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

（1）．用邻接表做存储结构,写一个D_搜索算法；（15分） （2）．用 D_搜索方法的访问次序和相应的生成树，当从某顶点出发搜索它的邻接点，请按邻接点序号递增序搜索，以使答案唯一。（5分）【中科院1998六（20分）】

28．令G=（V，E）为一个有向无环图，编写一个给图G中每一个顶点赋以一个整数序号的算法，并满足以下条件：若从顶点i至顶点j有一条弧则应使i

【复旦大学 1997 六 （13分）】

31. 设图用邻接表表示，写出求从指定顶点到其余各顶点的最短路径的Dijkstra 算法。

要求：（1）．对所用的辅助数据结构，邻接表结构给以必要的说明；（6分）

（2）．写出算法描述。(C,类-Pascal,类-C均可)（14分） 【南京理工大学 1996 四、1 （20分）】

类似本题的另外叙述有： （1）写出求从某个源点到其余各顶点最短路径的Dijkstra算法。要求说明主要的数据结

构及其作用，最后针对所给有向图，利用该算法，求V0到各顶点的最短距离和路线，即填写下表：

终点 V1 V2 V3 V4 V5 Vj V2 50V010V15V220 1040V530V420V3从V0到到各终点的dist的值和最短距离和路线 V3 V4 V5

【山东师范大学 1999 六 （14分）】

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

【南京航空航天大学 2001 九 （10分）】

类似本题的另外叙述有： （1）假定有n个城市组成的一个公路网，且认为公路是有向的，并用代价邻接矩阵表示该网络。试设计从指定城市V1到其他城市的最短路径的算法。 【西安电子科技大学 1996 三（10分）】

33．给定n个村庄之间的交通图，若村庄i和j之间有道路，则将顶点i和j用边连接，边上的Wij表示这条道路的长度，现在要从这n个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院的路程最短?试设计一个解答上述问题的算法，并应用该算法解答如图所示的实例。【中国矿业大学 2000 十五 （15分）】 2 12 1 9 5 6 3 10 c 4 4 4 2 2 6 a 1 b 2 3 e 7 6 3 2 1 d 5 4 第33题图 第34题图 34、求解下面有向图的有关问题：（1）判断此有向图是否有强连通分量？若有请画出； （2）画出此有向图的十字链表存储结构；其顶点表结点为(data, firstin, firstout) ，其中data是 顶点的有关信息，firstin是指向以该顶点为弧头的第一条边的指针，firstout是指向以该顶点为弧尾的第一条边的指针。其表结点的结构为（tailvex ,headvex ,weight, hlink, tlink），其中tailvex，headvex分别为弧尾和弧头在图中的序号，weight是弧上的权值，hlink，tlink分别为指向弧头相同和弧尾相同的下一条边的指针。

（3）设其顶点a, b, c, d, e表示一个乡的5个村庄，弧上的权值表示为两村之间的距离；

① 求每个村庄到其它村庄的最短距离；

② 乡内要建立一所医院，问医院设在哪个村庄才能使各村离医院的距离较近。 【北京邮电大学 1997 五（15分）】

35．设计算法，求出无向连通图中距离顶点V0的最短路径长度（最短路径长度以边数为单位计算）为K的所有的结点，要求尽可能地节省时间。【西北大学 2001 七】

36．自由树(即无环连通图)T=(V,E)的直径是树中所有点对间最短路径长度的最大值,即T的直径定义为MAX D(u,v) ,这里D(u,v) （u,v∈V）表示顶点u到顶点v的最短路径长度(路径长度为路径中所包含的边数)。写一算法求T的直径,并分析算法的时间复杂度。(时间复杂度越小得分越高)

【中科院1999五、3（20分）】

37．求图的中心点的算法。设V是有向图G的一个顶点，我们把V的偏心度定义为：max{从w到v的最短距离|w是g中所有顶点}，如果v是有向图G中具有最小偏心度的顶点，则称顶点v是G的中心点。

【长沙铁道学院 1998 五、2 (10分)】

38．设G是含有n顶点（设顶点编号为1,2,?,n）的有向无环图。将G用如下定义的邻接

表存储：

TYPE arcptr=↑arcnode;

arcnode=RECORD{邻接表中的结点}

adjvex:1..n; nextarc:arcptr; END;

vexnode=RECORD{邻接表的表头结点}

vexnum: 1..n; firstarc:arcptr; mpl:integer END;

Hnodes=ARRAY[1..n] OF vexnode;

请编写一个非递归算法求G的每个顶点出发的最长路径的长度（每条弧的长度均为1）并存入mpl域中。 要求：首先写出算法思想，然后写算法过程。【山东科技大学 2001 六 （20分）】

39．图G有n个点，利用从某个源点到其余各点最短路径算法思想，设计一产生G的最小生成树的算法。

【东南大学 1994 四（18分）】

40．设G是一个用邻接表表示的连通无向图。对于G中某个顶点v，若从G中删去顶点v及与顶点v相关联的边后，G变成由两个或两个以上非空连通分量所组成的图，则称v是原来图G的一个关节顶点。如下图中，只有顶点4和顶点6是关节顶点，而其它顶点都不是关节顶点。试叙述寻找图G的所有关节顶点的算法，并用算法语言（PASCAL或C）编写一个实现你所给出的算法的程序。【复旦大学 1996 八 （20分）】

2 5 4 7 1 3 6

41．对于一个使用邻接表存储的有向图G，可以利用深度优先遍历方法，对该图中结点进行

拓扑排序。其基本思想是：在遍历过程中，每访问一个顶点，就将其邻接到的顶点的入度减一，并对其未访问的、入度为0的邻接到的顶点进行递归。 （1）．给出完成上述功能的图的邻接表定义（结构）：（4分） （2）．定义在算法中使用的全局辅助数组。（4分） （3）．写出在遍历图的同时进行拓扑排序的算法：（10分）

【东北大学 1999 五 (18分)】 【清华大学 1997 一（18分）】

42．欲用四种颜色对地图上的国家涂色，有相邻边界的国家不能用同一种颜色（点相交不算相邻）。

（1）．试用一种数据结构表示地图上各国相邻的关系，（６分）。 （2）．描述涂色过程的算法。（不要求证明）（１２分）。 【浙江大学2002八 （18分）】

第7章 图

一.选择题 1.A 19.AB 28.D 2.B 3.A 4.B 5.D 6.1B 6.2D 7.1B 7.2C 8.A 9.A 10.1C 27.B 12.× 24.× 36.√ 48. 10.2BDE 11.B 12.1B 12.2B 12.3D 13.B 29.B 30.A 31.C 32.B 14.C 15.C 16.D 17.D 18.1C 18.2C 11.√ 23.× 35.× 47.20.B 21.1C 21.2A 21.3B 21.4A 22.A 23.A 24.D 25.A 26.A 二.判断题 1.√ 2. × 13.√ 25.× 37.14.× 26.√ 38.3.× 4.× 5.× 6.√ 7.× 8.× 9.× 10.× 15.× 27.× 39.16.× 28.√ 40.17.√ 29.× 41.18.× 30.× 42.19.× 31.√ 43.20.× 32.√ 44.21.× 33.× 45.22.× 34.× 46.× 49.× × × × √ × × √ × × × √ 部分答案解释如下。

2. 不一定是连通图，可能有若干连通分量 11. 对称矩阵可存储上（下）三角矩阵 14．只有有向完全图的邻接矩阵是对称的 16. 邻接矩阵中元素值可以存储权值 21. 只有无向连通图才有生成树 22. 最小生成树不唯一，但最小生成树上权值之和相等

26. 是自由树，即根结点不确定

35. 对有向无环图，拓扑排序成功；否则，图中有环，不能说算法不适合。

42. AOV网是用顶点代表活动，弧表示活动间的优先关系的有向图,叫顶点表示活动的网。 45. 能求出关键路径的AOE网一定是有向无环图 46. 只有该关键活动为各关键路径所共有，且减少它尚不能改变关键路径的前提下，才可缩短工期。

48．按着定义，AOE网中关键路径是从“源点”到“汇点”路径长度最长的路径。自然，关键路径上活动的时间延长多少，整个工程的时间也就随之延长多少。

三．填空题

1.有n个顶点，n-1条边的无向连通图 2.有向图的极大强连通子图 3. 生成树

4. 45 5. n(n-1)/2 6 . 7. 9 8. n

9. 2(n-1) 10. N-1 11. n-1 12. n 13. N-1 14. n 15. N

16. 3 17. 2（N-1） 18. 度出度 19. 第I列非零元素个数 20.n 2e

21.(1)查找顶点的邻接点的过程 (2)O(n+e) (3)O(n+e) (4)访问顶点的顺序不同 (5)队列和栈

22. 深度优先 23.宽度优先遍历 24.队列

25.因未给出存储结构，答案不唯一。本题按邻接表存储结构，邻接点按字典序排列。

F A B C D F I A C E D K E J B K I J 25题（1） 25题（2） 26.普里姆（prim）算法和克鲁斯卡尔（Kruskal）算法 27.克鲁斯卡尔

2

28.边稠密边稀疏 29. O(eloge）边稀疏 30.O(n） O(eloge) 31.(1）（Vi，Vj）边上的权值都大的数（2）1 负值（3）为负边

32.(1)n-1 (2)普里姆 (3)最小生成树 33.不存在环 34.递增负值 35.160

2

36.O(n） 37. 50，经过中间顶点④ 38. 75 39.O(n+e） 40.(1）活动（2）活动间的优先关系（3）事件（4）活动边上的权代表活动持续时间 41.关键路径 42.（1）某项活动以自己为先决条件 （2）荒谬（3）死循环

43.（1）零（2）Vk度减1，若Vk入度己减到零，则Vk顶点入栈（3）环

44.（1）p<>nil (2)visited[v]=true (3)p=g[v].firstarc (4)p=p^.nextarc

45.(1)g[0].vexdata=v (2)g[j].firstin (3)g[j].firstin (4)g[i].firstout (5)g[i].firstout (6)p^.vexj (7)g[i].firstout (8)p:=p^.nexti (9)p<>nil (10)p^.vexj=j

(11)firstadj(g,v0) (12)not visited[w] (13)nextadj(g,v0,w)

46.(1)0 (2)j (3)i (4)0 (5)indegree[i]==0 (6)[vex][i] (7)k==1 (8)indegree[i]==0

47.(1)p^.link:=ch[u].head (2)ch[u].head:=p (3)top<>0 (4)j:=top (5)top:=ch[j].count

(6)t:=t^.link

48.（1）V1 V4 V3 V6 V2 V5(尽管图以邻接表为存储结构，但因没规定邻接点的排列，所以结果是不唯一的。本答案是按邻接点升序排列给出的。)

（2）①top==-1 ②top=graph[j].count ③graph[k].count==0

四.应用题 1．（1）G1最多n(n-1)/2条边，最少n-1条边 (2) G2最多n(n-1)条边，最少n条边 (3) G3最多n(n-1)条边，最少n-1条边 (注：弱连通有向图指把有向图看作无向图时，仍是连通的) 2．n-1，n 3.分块对称矩阵

4．证明：具有n个顶点n-1条边的无向连通图是自由树，即没有确定根结点的树，每个结点均可当根。若边数多于n-1条，因一条边要连接两个结点，则必因加上这一条边而使两个结点多了一条通路，即形成回路。形成回路的连通图不再是树（在图论中树定义为无回路的连通图）。

5．证明：该有向图顶点编号的规律是让弧尾顶点的编号大于弧头顶点的编号。由于不允许从某顶点发出并回到自身顶点的弧，所以邻接矩阵主对角元素均为0。先证明该命题的充分条件。由于弧尾顶点的编号均大于弧头顶点的编号，在邻接矩阵中，非零元素（A[i][j]=1）自然是落到下三角矩阵中；命题的必要条件是要使上三角为0，则不允许出现弧头顶点编号大于弧尾顶点编号的弧，否则，就必然存在环路。（对该类有向无环图顶点编号，应按顶点出度顺序编号。）

2

6．设图的顶点个数为n(n≥0)，则邻接矩阵元素个数为n，即顶点个数的平方，与图的边数无关。 7．（1）n(n-1)， n

6

(2) 10，不一定是稀疏矩阵（稀疏矩阵的定义是非零个数远小于该矩阵元素个数，且分布无规律） （3）使用深度优先遍历，按退出dfs过程的先后顺序记录下的顶点是逆向拓扑有序序列。若在执行dfs(v)未退出前，出现顶点u到v的回边，则说明存在包含顶点v和顶点u的环。 8．(1) （2）开始结点：（入度为0）K1，K2，终端结点（出3 2 度为0）K6，K7 。 （3）拓扑序列1 1，K2，K3，K4，K5，K6，K8，K9，K7 9 K4 5 K2，K1，K3，K4，K5，K6，K8，K9，K7 8 K1或7 K2，之后，若遇多个入度为6 规则：开始结点为0的顶点，按顶点编号顺序选择。 （4）

8（4）邻接表和逆邻接表 9．（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)

10．图G的具体存储结构略。

2

邻接矩阵表示法，有n个顶点的图占用n个元素的存储单元，与边的个数无关，当边数较少时，存储效率较低。这种结构下，对查找结点的度、第一邻接点和下一邻接点、两结点间是否有边的操作有利，对插入和删除顶点的操作不利。

邻接表表示法是顶点的向量结构与顶点的邻接点的链式存储结构相结合的结构，顶点的向量结构含有n（n≥0）个顶点和指向各顶点第一邻接点的指针，其顶点的邻接点的链式存储结构是根据顶点的邻接点的实际设计的。这种结构适合查找顶点及邻接点的信息，查顶点的度，增加或删除顶点和边（弧）也很方便，但因指针多占用了存储空间，另外，某两顶点间是否有边（弧）也不如邻接矩阵那么清楚。对有向图的邻接表，查顶点出度容易，而查顶点入度却困难，要遍历整个邻接表。要想查入度象查出度那样容易，就要建立逆邻接表。无向图邻接表中边结点是边数的二倍也增加了存储量。

十字链表是有向图的另一种存储结构，将邻接表和逆邻接表结合到一起，弧结点也增加了信息（至少弧尾，弧头顶点在向量中的下标及从弧尾顶点发出及再入到弧头顶点的下一条弧的四个信息）。查询顶点的出度、入度、邻接点等信息非常方便。

邻接多重表是无向图的另一种存储结构，边结点至少包括5个域：连接边的两个顶点在顶点向量中的下标，指向与该边相连接的两顶点的下一条边的指针，以及该边的标记信息（如该边是否被访问）。边结点的个数与边的个数相同，这是邻接多重表比邻接表优越之处。 11．

已知顶点i，找与i相邻的顶点j的规则如下：在顶点向量中，找到顶点i，顺其指针找到第一个边结点（若其指针为空，则顶点i无邻接点）。在边结点中，取出两顶点信息，若其中有j，则找到顶点j；否则，沿从i发出的另一条边的指针（ilink）找i的下一邻接点。在这种查找过程中，若边结点中有j，则查找成功；若最后ilink为空，，则顶点i无邻接点j。

12．按各顶点的出度进行排序。n个顶点的有向图，其顶点最大出度是n-1，最小出度为0。这样排序后，出度最大的顶点编号为1，出度最小的顶点编号为n。之后，进行调整，即若存在弧，而顶点j的出度大于顶点i的出度，则将把j编号在顶点i的编号之前。本题算法见下面算法设计第28题。

13．采用深度优先遍历算法，在执行dfs(v)时，若在退出dfs(v)前，碰到某顶点u ，其邻接点是已经访问的顶点v，则说明v的子孙u有到v的回边，即说明有环，否则，无环。（详见下面算法题13）

14．深度优先遍历序列：125967384

宽度优先遍历序列：123456789 注：（1）邻接表不唯一，这里顶点的邻接点按升序排列 （2）在邻接表确定后，深度优先和宽度优先遍历序列唯一 （3）这里的遍历，均从顶点1开始 15．（1）V1V2V4V3V5V6 （2）V1V2V3V4V5V6 16.(1)

1 4 5 3 2

7 6

8 9 10

16题（3）宽度优先生成树

10 9 1 2 5 3 4 7 6 8 （2）深度优先生成树

为节省篇幅，生成树横画，下同。

17．设从顶点1开始遍历，则深度优先生成树(1)和宽度优先生成树(2)为： 1 4 3 2 1 2 3 4 5 5 图17(1) 图17(2)

18．遍历不唯一的因素有：开始遍历的顶点不同；存储结构不同；在邻接表情况下邻接点的顺序不同。 19．（1）邻接矩阵：（6*6个元素）*2字节/元素=72字节

邻接表：表头向量6*（4+2）+边结点9*(2+2+4)*2=180字节

邻接多重表：表头向量6*（4+2）+边结点9*（2+2+2+4+4）=162字节

邻接表占用空间较多，因为边较多，边结点又是边数的2倍，一般来说，邻接矩阵所占空间与边个数无关（不考虑压缩存储），适合存储稠密图，而邻接表适合存储稀疏图。邻接多重表边结点个数等于边数，但结点中增加了一个顶点下标域和一个指针域。 1 2 3 5 4 （2）因未确定存储结构，从顶点1开始的DFS树 1 6 5 4 2 不唯一，现列出两个：

20．未确定存储结构，其DFS树不唯一，其中之一（按邻接点逆序排列）是

1 8 9 3 10 2 7

4 6 5

（2）关节点有3，1，8，7，2 21．（1） A

F B C E

D

（2）AFEDBC

22．设邻接表（略）中顶点的邻接点按顶点编号升序排列（V1编号为1）

（1） 广度优先搜索序列：V1V2V3V4V5V6V7V8 （2） 深度优先搜索序列：V1V2V4V8V5V3V6V7 23．（1）略（2）V1V2V5V3V4V6 (4) V1V2V3V4V5V6 V1 (3) V4 (5) V6 V3 V4 V2 V1 V2 V5 V3 V6 V5 6 3

(6）见本章五算法设计第6题

24．设该图用邻接表存储结构存储，顶点的邻接点按顶点编号升序排列 (1)ABGFDEC (2)EACFBDG (3)

A 2 A 2 2 A A 2 D D B D 3 1 D 3 3 F F G G 1 F 3

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

26．无向连通图的生成树包含图中全部n个顶点，以及足以使图连通的n-1条边。而最小生成树则是各边权值之和最小的生成树。从算法中WHILE（所剩边数>=顶点数）来看，循环到边数比顶点数少1（即n-1）停止，这符合n个顶点的连通图的生成树有n-1条边的定义；由于边是按权值从大到小排序，删去的边是权值大的边，结果的生成树必是最小生成树；算法中“若图不再连通，则恢复ei”，含义是必须保留使图连通的边，这就保证了是生成树，否则或者是有回路，或者成了连通分量，均不再是生成树。

27．Prim算法构造最小生成树的步骤如24题所示，为节省篇幅，这里仅用Kruskal算法，构造最小生成树过程如下：（下图也可选(2,4)代替(3,4),(5,6)代替(1,5)） 1 2 5 9 即 10 6 11 3 2 5 3 1 9 1 2 10 5 3 6 6 11 6 4 6 4 5 A 2 4 D B C 3 3 F G 1 A 2 4 D C B 3 E 1 3 F G 1 28．（1）最小生成树的定义见上面26题

（2）最小生成树有两棵。

（限于篇幅，下面的生成树只给出顶点集合和边集合，边以三元组（Vi,Vj,W）形式），其中W代表权值。

V（G）={1，2，3，4，5} E1(G)={(4，5，2)，（2，5，4），（2，3，5），（1，2，7）}；

E2(G)={(4，5，2），（2，4，4），（2，3，5），（1，2，

7）}

29．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），（1，2，18）} 30．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 （1，2，5）}

1 2 注：（或将（3，4，3）换成（7，8，3）） 1 1 2 31．设顶点集合为{1，2，3，4，5，6}， 4 3 由右边的逻辑图可以看出，在{1，2，3}和{4，5，6}回路中， 1 3 1 各任选两条边，加上（2，4），则可构成9棵不同的最小生成树。 6 5 1 32．（1）邻接矩阵略

（2） Y Closedge 2 Vex Lowcost Vex Lowcost 3 4 ① ① 2 3 ① ② 3 [ 错误 ] 系统维护中

五.算法设计题

1. void CreatGraph (AdjList g)

//建立有n个顶点和m 条边的无向图的邻接表存储结构 {int n,m;

scanf(\

for (i =1,i<=n;i++)//输入顶点信息,建立顶点向量

{scanf(&g[i].vertex); g[i].firstarc=null;} for (k=1;k<=m;k++)//输入边信息 {scanf(&v1,&v2);//输入两个顶点

i=GraphLocateVertex (g,v1); j=GraphLocateVertex (g,v2); //顶点定位 p=(ArcNode *)malloc(sizeof(ArcNode));//申请边结点

p->adjvex=j; p->next=g[i].firstarc; g[i].firstarc=p;//将边结点链入 p=(ArcNode *)malloc(sizeof(ArcNode));

p->adjvex=i; p->next=g[j].firstarc; g[j].frstarc=p; }

}//算法CreatGraph结束

2. void CreatAdjList(AdjList g)

//建立有向图的邻接表存储结构 {int n;

scanf(\\,&n); for (i=1;i<=n;j++)

{scanf(&g[i].vertex); g[i].firstarc=null;}//输入顶点信息 scanf(&v1,.&v2);

while(v1&&v2)//题目要求两顶点之一为0表示结束 {i=GraphLocateVertex(g2,v1);

p=(ArcNode*)malloc(sizeof(ArcNode));

p->adjvex=j; p->next=g[i].firstarc; g[i].firstarc=p;

scanf(&v1,&v2); } }

3. void CreatMGraph(AdjMulist g)

//建立有n个顶点e条边的无向图的邻接多重表的存储结构 {int n,e;

scanf(\

for(i=1,i<=n;i++) //建立顶点向量

{ scanf(&g[i].vertex); g[i].firstedge=null;} for(k=1;k<=e;k++) //建立边结点 {scanf(&v1,&v2);

i=GraphLocateVertex(g,v1); j=GraphLocateVertex(g,v2);

p=(ENode *)malloc(sizeof(ENode)); p->ivex=i; p->jvex=j; p->ilink=g[i].firstedge; p->jlink=g[j].firstedge;

g[i].firstedge=p; g[j].firstedge=p; }

}//算法结束

4. void CreatOrthList(OrthList g)

//建立有向图的十字链表存储结构 {int i,j,v; //假定权值为整型 scanf(\

for(i=1,i<=n;i++) //建立顶点向量

{ scanf(&g[i].vertex); g[i].firstin=null; g[i].firstout=null;} scanf(\

while (i && j && v) //当输入i,j,v之一为0时,结束算法运行 {p=(OrArcNode *)malloc(sizeof(OrArcNode)); //申请结点

p->headvex=j; p->tailvex=i; p->weight=v; //弧结点中权值域 p->headlink=g[j].firstin; g[j].firstin=p; p->tailink=g[i].firstout; g[i].firstout=p;

scanf(\ } }算法结束

[算法讨论] 本题已假定输入的i和j是顶点号,否则,顶点的信息要输入,且用顶点定位函数求出顶点在顶点向量中的下标。图建立时，若已知边数（如上面1和2题），可以用for循环；若不知边数，可用while循环（如本题），规定输入特殊数（如本题的零值）时结束运行。本题中数值设为整型，否则应以和数值类型相容的方式输入。 5．void InvertAdjList(AdjList gin,gout）

//将有向图的出度邻接表改为按入度建立的逆邻接表

{for (i=1;i<=n;i++)//设有向图有n个顶点，建逆邻接表的顶点向量。

{gin[i].vertex=gout[i].vertex; gin.firstarc=null; } for (i=1;i<=n;i++) //邻接表转为逆邻接表。

{p=gout[i].firstarc;//取指向邻接表的指针。 while (p!=null)

{ j=p->adjvex;

s=(ArcNode *)malloc(sizeof(ArcNode));//申请结点空间。 s->adjvex=i; s->next=gin[j].firstarc; gin[j].firstarc=s; p=p->next;//下一个邻接点。 }//while }//for }

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 }//算法结束

7. void AdjMatrixToAdjList( AdjMatrix gm, AdjList gl )

//将图的邻接矩阵表示法转换为邻接表表示法。 {for (i=1;i<=n;i++) //邻接表表头向量初始化。 {scanf(&gl[i].vertex); gl[i].firstarc=null;} for (i=1;i<=n;i++) for (j=1;j<=n;j++) if (gm[i][j]==1)

{p=(ArcNode *)malloc(sizeof(ArcNode)) ;//申请结点空间。

p->adjvex=j;//顶点I的邻接点是j

p->next=gl[i].firstarc; gl[i].firstarc=p; //链入顶点i的邻接点链

表中

}

}//end

[算法讨论] 算法中邻接表中顶点在向量表中的下标与其在邻接矩阵中的行号相同。 8.[题目分析] 在有向图中，判断顶点Vi和顶点Vj间是否有路径，可采用遍历的方法，从顶点Vi出发，不论是深度优先遍历（dfs）还是宽度优先遍历（bfs），在未退出dfs或bfs前,若访问到Vj，则说明有通路，否则无通路。设一全程变量flag。初始化为0，若有通路，则flag=1。

算法1：int visited[]=0; //全局变量，访问数组初始化

int dfs(AdjList g , vi)

//以邻接表为存储结构的有向图g，判断顶点Vi到Vj是否有通路,返回1或0表示有或无

{ visited[vi]=1; //visited是访问数组，设顶点的信息就是顶点编号。 p=g[vi].firstarc; //第一个邻接点。 while ( p!=null)

{ j=p->adjvex;

if (vj==j) { flag=1; return（1）;} //vi 和 vj 有通路。 if (visited[j]==0) dfs(g,j); p=p->next； }//while if (!flag) return(0); }//结束

[算法讨论] 若顶点vi和vj 不是编号，必须先用顶点定位函数,查出其在邻接表顶点向量中的下标i和j。下面算法2输出vi 到 vj的路径，其思想是用一个栈存放遍历的顶点，遇到顶点vj时输出路径。

算法2：void dfs(AdjList g , int i)

//有向图g的顶点vi（编号i）和顶点vj（编号j）间是否有路径，如有，则输出。 {int top=0,stack[]; //stack是存放顶点编号的栈

visited[i]=1; //visited 数组在进入dfs前已初始化。 stack[++top]=i;

p=g[i].firstarc; /求第一个邻接点. while (p)

{if (p->adjvex==j)

{stack[++top]=j; printf( \顶点 vi 和 vj 的路径为：\\n\for (i=1; i<=top; i++) printf( \

}//if

elseif (visited[p->adjvex]==0) {dfs(g,g->adjvex); top--; p=p->next;}//elseif }//while }//结束算法2

算法3：本题用非递归算法求解。

int Connectij (AdjList g , vertype vi , vj )

//判断n个顶点以邻接表表示的有向图g中，顶点 Vi 各Vj 是否有路径，有则返回1，否则返回0。

{ for (i=1;i<=n;i++) visited[i]=0; //访问标记数组初始化。

i=GraphLocateVertex(g,vi); //顶点定位，不考虑 vi或 vj不在图中的情况。 j=GraphLocateVertex(g,vj);

int stack[],top=0;stack[++top]=i; while(top>0)

{k=stack[top--]; p=g[k].firstarc;

while(p!=null && visited[p->adjvex]==1) p=p->next; //查第k个链表中第一个未访问的弧结点。

if(p==null) top--; else {i=p->adjvex;

if(i==j) return(1); //顶点vi和vj 间有路径。 else {visited[i]=1; stack[++top]=i;}//else }//else

}while

return(0); } //顶点vi和vj 间无通路。 9. void DeletEdge(AdjList g,int i,j)

//在用邻接表方式存储的无向图g中，删除边(i,j)

{p=g[i].firstarc; pre=null; //删顶点i 的边结点(i,j),pre是前驱指针

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;} //沿链表继续查找

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。 10. void DeleteArc（AdjList g,vertype vi,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;} }//结束

11. void InsertArc ( OrthList g ,vertype vi,vj) //在以十字链表示的有向图g中插入弧 { i=GraphLocateVertex(g,vi); //顶点定位. j=GraphLocateVertex(g,vj);

p=(OrArcNode *)malloc(sizeof(OrArcNode));

p=headvex=j; p=tailvex=i; //填写弧结点信息并插入十字链表。 p->headlink=g[j].firstin; g[j].firstin=p; p->taillink=g[i].firstout; g[i].firstout=p; }//算法结束 12. [题目分析]在有向图的邻接表中，求顶点的出度容易，只要简单在该顶点的邻接点链表中查结点个数即可。而求顶点的入度，则要遍历整个邻接表。 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的入度. } 13. [题目分析]有向图判断回路要比无向图复杂。利用深度优先遍历，将顶点分成三类：未访问；已访问但其邻接点未访问完;已访问且其邻接点已访问完。下面用0，1，2表示这三种状态。前面已提到，若dfs（v）结束前出现顶点u到v的回边，则图中必有包含顶点v和u的回路。对应程序中v的状态为1，而u是正访问的顶点，若我们找出u的下一邻接点的状态为1，就可以输出回路了。

void Print(int v,int start ) //输出从顶点start开始的回路。 {for(i=1;i<=n;i++)

if(g[v][i]!=0 && visited[i]==1 ) //若存在边（v,i），且顶点i的状态为1。 {printf(“%d”,v); if(i==start) printf(“\\n”); else Print(i,start);break;}//if }//Print

void dfs(int v) {visited[v]=1;

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

if (g[v][j]!=0) //存在边(v,j)

if (visited[j]!=1) {if (!visited[j]) dfs(j); }//if else {cycle=1; Print(j,j);} visited[v]=2;

}//dfs

void find_cycle() //判断是否有回路，有则输出邻接矩阵。visited数组为全局变量。 {for (i=1;i<=n;i++) visited[i]=0;

for (i=1;i<=n;i++ ) if (!visited[i]) dfs(i);

}//find_cycle

14．[题目分析]有几种方法判断有向图是否存在环路，这里使用拓扑排序法。对有向图的顶点进行拓扑排序，若拓扑排序成功，则无环路；否则，存在环路。题目已假定有向图用十字链表存储，为方便运算，在顶点结点中，再增加一个入度域indegree，存放顶点的入度。入度为零的顶点先输出。为节省空间，入度域还起栈的作用。值得注意的是，在邻接表中，顶点的邻接点非常清楚，顶点的单链表中的邻接点域都是顶点的邻接点。由于十字链表边（弧）结点个数与边（弧）个数相同（不象无向图边结点个数是边的二倍），因此，对某顶点v, 要判断其邻接点是headvex还是tailvex。 int Topsor(OrthList g)

//判断以十字链表为存储结构的有向图g是否存在环路，如是，返回1，否则，返回0。

{int top=0; //用作栈顶指针

for (i=1;i<=n;i++) //求各顶点的入度。设有向图g有n个顶点，初始时入度域均为0

{p=g[i].firstin; //设顶点信息就是顶点编号，否则，要进行顶点定位 while(p)

{g[i].indegree++; //入度域增1

if (p->headvex==i) p=p->headlink; else p=p->taillink; //找顶点i的邻

接点

}//while(p) }//for

for (i=1;i<=n;i++) //建立入度为0的顶点的栈 if (g[i].indegree==0) {g[i].indegree=top; top=i; } m=0; //m为计数器，记输出顶点个数 while (top<>0)

{i=top; top=g[top].indegree; m++; //top指向下一入度为0的顶点 p=g[i].firstout;

while (p) //处理顶点i的各邻接点的入度

{if (p->tailvex==i) k=p->headvex; else k=p->tailvex;}//找顶点i的邻接点

g[k].indegree--; //邻接点入度减1

if (g[k].indegree==0) {g[k].indegree=top; top=k; } //入度为0的顶点再入栈

if (p->headvex==i) p=p->headlink; else p=p->taillink;//找顶点i的下

一邻接点

}//while (p) }// while (top<>0)

if (m

15. int FirstAdj(AdjMuList g , vertype v)

//在邻接多重表g中，求v的第一邻接点，若存在，返回第一邻接点，否则，返回0。 {i=GraphLocateVertex(g,v); //确定顶点v在邻接多重表向量中的下标，不考虑不存在v的情况。

p=g[i].firstedge; //取第一个边结点。 if (p==null ) return (0);

else {if (ivex==i) return (jvex); elsereturn (ivex);}

//返回第一邻接点，ivex和jvex中必有一个等于i

}// FirstAdj

16. [题目分析]本题应使用深度优先遍历，从主调函数进入dfs(v)时，开始记数，若退出dfs()前，已访问完有向图的全部顶点（设为n个），则有向图有根，v为根结点。将n个顶点从1到n编号，各调用一次dfs()过程，就可以求出全部的根结点。题中有向图的邻接表存储结构、记顶点个数的变量、以及访问标记数组等均设计为全局变量。建立有向图g的邻接表存储结构参见上面第2题，这里只给出判断有向图是否有根的算法。

int num=0， visited[]=0 //num记访问顶点个数,访问数组visited初始化。 const n=用户定义的顶点数;

AdjList g ; //用邻接表作存储结构的有向图g。 void dfs(v)

{visited [v]=1; num++; //访问的顶点数＋1

if (num==n) {printf(“%d是有向图的根。\\n”,v); num=0;}//if p=g[v].firstarc; while (p)

{if (visied[p->adjvex]==0) dfs (p->adjvex);

p=p->next;} //while

visited[v]=0; num--; //恢复顶点v

}//dfs

void JudgeRoot()

//判断有向图是否有根，有根则输出之。 {staticint i ;

for (i=1;i<=n;i++ ) //从每个顶点出发，调用dfs()各一次。 {num=0; visited[1..n]=0; dfs(i); } }// JudgeRoot

算法中打印根时，输出顶点在邻接表中的序号（下标），若要输出顶点信息，可使用g[i].vertex。

17. [题目分析] 使用图的遍历可以求出图的连通分量。进入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\if }//Count

算法中visited[]数组是全程变量，每个连通分量的顶点集按遍历顺序输出。这里设顶点信息就是顶点编号，否则应取其g[i].vertex分量输出。 18. 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(\visited[p->adjvex]=1; QueueIn(Q,p->adjvex);}//if

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\if }//BFSCOM

19.请参见上题18。HEAD，MARK，VER，LINK相当于上题GL，visited，adjvex，next。 20. 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); 21. （１）限于篇幅，邻接表略。

（２）在邻接点按升序排列的前提下，其dfs和bfs序列分别为BADCEF和BACEDF。 （３）void dfs(v)

{i=GraphLocateVertex(g ,v); //定位顶点 visited[i]=1; printf(v); //输出顶点信息 p=g[i].firstarc; while (p)

{ if (visited[p->adjvex]==0) dfs(g[p->adjvex].vertex); p=p->next;

}//while

}//dfs

void traver( )

//深度优先搜索的递归程序；以邻接表表示的图g是全局变量。

{ for (i=1;i<=n;i++) visited[i]=0; //访问数组是全局变量初始化。 for (vi=v1;vi<=vn;vi++)

if (visited[GraphLocateVertex(g，vi)]==0) dfs(vi); }//算法结束。 22. [题目分析]强连通图指从任一顶点出发，均可访问到其它所有顶点，故这里只给出dfs()过程。

PROC dfs(g:AdjList , v0:vtxptr)

//从v0出发，深度优先遍历以邻接表为存储结构的强连通图g。

TYPE stack=ARRAY[1..n] OF arcptr; //栈元素为弧结点指针，n为顶点个数。 s:stack; top:integer; top:=0 visited[v0]:=1;

write(v0:4); //设顶点信息就是顶点编号；否则要顶点定位。 p:=g[v0]^.firstarc;

WHILE (top>0 || p!=NIL) DO BEGINWHILE (p!= NIL) DO

IF (visited[p^.adjvex]=1) THEN p:=p^.next; //查未访问的邻接点。 ELSEBEGIN w:=p^.adjvex; visited[w]:=1; top:=top+1; s[top]:=p; p:=g[w].firstarc ;

END； //深度优先遍历。

IF (top>0) THEN BEGIN p:=s[top]; top:=top-1; p:=p^.next END;

END； ENDP；

23. [题目分析] 本题是对无向图Ｇ的深度优先遍历，dfs算法上面已有几处（见20-22）。这里仅给出将连通分量的顶点用括号括起来的算法。为了得出题中的输出结果，各顶点的邻接点要按升序排列。 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 (\if

}//Traver

24.void visit(vertype v) //访问图的顶点v。

void initqueue (vertype Q[]) //图的顶点队列Ｑ初始化。 void enqueue (vertype Q[] ,v) //顶点v入队列Ｑ。 vertype delqueue (vertype Q[]) //出队操作。

int empty (Q) //判断队列是否为空的函数，若空返回１，否则返回０。

vertype firstadj(graph g ,vertype v)//图g中v的第一个邻接点。

vertype nextadj(graph g ,vertype v ,vertype w)//图g中顶点v的邻接点中在w后的邻接点

void bfs (graph g ,vertype v0)

//利用上面定义的图的抽象数据类型，从顶点v0出发广度优先遍历图g。 {visit(v0);

visited[v0]=1; //设顶点信息就是编号，visited是全局变量。 initqueue(Q); enqueue(Q,v0); //v0入队列。 while (!empty(Q))

{v=delqueue(Q); //队头元素出队列。

w=firstadj(g ,v); //求顶点v的第一邻接点 while (w!=0) //w!=0表示w存在。

{if (visited[w]==0) //若邻接点未访问。

{visit(w); visited[w]=1; enqueue(Q,w);}//if

w=nextadj(g,v,w); //求下一个邻接点。 }//while }//while }//bfs

void Traver()

//对图g进行宽度优先遍历，图g是全局变量。 {for (i=1;i<=n;i++) visited[i]=0; for (i=1;i<=n;i++)

if (visited[i]==0) bfs(i); } //Traver

25.[题目分析] 本题应使用深度优先遍历。设图的顶点信息就是顶点编号，用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( \//if

p=g[v0].firstarc; while (p)

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

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

26. 与上题类似，这里给出非递归算法，顶点信息仍是编号。 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( \printf( \if

else { visited[i]=1; s[++top]=i; } //else深度优先遍历。 }//else }//while }// AllSPdfs

类似本题的另外叙述的第（2）题 ：u到v有三条简单路径：uabfv，ucdv，ucdefv。 27. （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;

1 } //下一个邻接点

}//while(top>0) 2 3 4 } //if 7 }//D_BFS

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

28，[题目分析] 本题的含义是对有向无环图(DAG)的顶点，以整数适当编号后，可使其邻接矩阵中对角线以下元素全部为零。根据这一要求，可以按各顶点出度大小排序，使出度最大的顶点编号为1，出度次大者编号为2，出度为零的顶点编号为n。这样编号后，可能出现顶点编号i，且i>j，则使顶点j的编号在顶点i的编号之前。 void Adjust(AdjMatrix g1 ,AdjMatrix g2)

//对以邻接矩阵存储的DAG图g1重新编号，使若有，则编号i

{typedefstruct { int vertex ,out ,count }node ; //结点结构：顶点，出度，计数。

node v[]; //顶点元素数组。 int c[]; //中间变量

for (i=1;i<=n;i++) //顶点信息数组初始化，设图有n个顶点。

{v[i].vertex=i; v[i].out=0; v[i].count=1; c[i]=1;} //count=1为最小 for (i=1;i<=n;i++) //计算每个顶点的出度。 for (j=1;j<=n;j++) v[i].out+=g1[i][j];

for (i=n;i>=2;i--) //对v的出度域进行计数排序，出度大者，count域中值小。 for (j=i-1;j>=1;j--)

if (v[i].count<=v[j].count) v[i].count++; else v[j].count++;

for (i=1;i<=n;i++) //第二次调整编号。若且i>j，则顶点j的编号在顶点i的编号之前

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

if(g1[i][j]==1 && v[i].count>v[j].count) {v[i].count=v[j].count;v[j].count++;} for (i=n;i>=2;i--)) //对v的计数域v[i].count排序，按count域从小到大顺序存到数组c中。

for (j=i-1;j>=1;j--)

if (v[i].count

for (i=1;i<=n;i++) v[i].count=c[i]; //将最终编号存入count 域中。 for (i=1;i<=n;i++) for (j=1;j<=n;j++)

g2[v[i].count][v[j].count]=g1[v[i].vertex][v[j].vertex]; }//算法结束 29. 二部图 非二部图 [题目分析] 将顶点放在两个集合V1和 V2。对每个顶点，检查其和邻接点是否在同一 个集合中，如是，则为非二部图。为此，用整数1和2表示两个集合。再用一队列结构存放图中访问的顶点。

int BPGraph (AdjMatrix g)

//判断以邻接矩阵表示的图g是否是二部图。

{int s[]; //顶点向量，元素值表示其属于那个集合（值1和2表示两个集合） int Q[];//Q为队列，元素为图的顶点，这里设顶点信息就是顶点编号。

int f=0,r,visited[]; //f和r分别是队列的头尾指针,visited[]是访问数组

for (i=1;i<=n;i++) {visited[i]=0;s[i]=0;} //初始化，各顶点未确定属于那个集合 Q[1]=1; r=1; s[1]=1;//顶点1放入集合S1

while(f

{v=Q[++f]; if (s[v]==1) jh=2; else jh=1;//准备v的邻接点的集合号 if (!visited[v])

{visited[v]=1; //确保对每一个顶点，都要检查与其邻接点不应在一个集合中

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

if (g[v][j]==1){if (!s[j]) {s[j]=jh; Q[++r]=j;} //邻接点入队列 elseif (s[j]==s[v]) return(0);} //非二部图 }//if (!visited[v]) }//while

return(1); }//是二部图

[算法讨论] 题目给的是连通无向图，若非连通，则算法要修改。

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

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

{typedefstruct {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条边。限于篇幅，这些算法不再写出。 31. [题目分析]求单源点最短路径问题，存储结构用邻接表表示，这里先给出所用的邻接表中的边结点的定义：struct node {int adjvex,weight; struct node *next;}p;

void Shortest_Dijkstra(AdjList cost ,vertype v0)

//在带权邻接表cost中，用Dijkstra方法求从顶点v0到其它顶点的最短路径。 {int dist[],s[]; //dist数组存放最短路径，s数组存顶点是否找到最短路径的信息。

for (i=1;i<=n;i++) {dist[i]=INFINITY; s[i]=0; } //初始化，INFINITY是机器中最大的数

s[v0]=1;

p=g[v0].firstarc;

while(p) //顶点的最短路径赋初值

{dist[p->adjvex]=p->weight; p=p->next;}

for (i=1;i

if (s[j]==0 && dist[j]

while(p) //修改从v0到其它顶点的最短路径 {j=p->adjvex;

if (s[j]==0 && dist[j]>dist[u]+p->weight) dist[j]=dist[u]+p->weight; p=p->next; }

}// for (i=1;i

32. 本题用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]; }//算法结束 33. [题目分析] 该题可用求每对顶点间最短路径的FLOYD算法求解。求出每一顶点（村庄）到其它顶点（村庄）的最短路径。在每个顶点到其它顶点的最短路径中，选出最长的一条。因为有n个顶点，所以有n条, 在这n条最长路径中找出最短一条，它的出发点（村庄）就是医院应建立的村庄。

void Hospital(AdjMatrix w,int n)

//在以邻接带权矩阵表示的n个村庄中，求医院建在何处，使离医院最远的村庄到医院的路径最短。

{for (k=1;k<=n;k++) //求任意两顶点间的最短路径 for (i=1;i<=n;i++) for (j=1;j<=n;j++)

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

for (j=1;j<=n;j++) //求从某村庄i（1<=i<=n）到其它村庄的最长路径。 if (w[i][j]>s) s=w[i][j];

if (s<=m) {m=s; k=i;}//在最长路径中，取最短的一条。m记最长路径，k记出发顶点的下标。

Printf(“医院应建在%d村庄，到医院距离为%d\\n”,i,m); }//for

}//算法结束

(6)

对以上实例模拟的过程略。在A矩阵中（见下图），各行中最大数依次是9，9，6，7，9，9。这几个最大数中最小者为6，故医院应建在第三个村庄中,离医院最远的村庄到医院的距离是6。

34. （１）该有向图的强连通分量有两个：一个是顶点a,另一个由b,c,e,d四个顶点组成。

（２）因篇幅有限从略，请参见本章四？

（３）用FLOYD算法求每对顶点间最短距离，其５阶方阵的初态和终态如下：

A=

(0)

A=

(5)

第33题结果矩阵

A=

(6)

由于要求各村离医院较近（不是上题中“离医院最远的村庄到医院的路径最短”），因此算法中求出矩阵终态后，将各列值相加，取最小的一个，该列所在村庄即为所求（本题答案是医院建在b村，各村到医院距离和是11），下面是求出各顶点间最短的路径后，求医院所在位置的语句段：

min=MAXINT ; //设定机器最大数作村庄间距离之和的初值。 k=1; //k设医院位置。 for (j=1;j<=n;j++) {m=0 ;

for (i=1;i<=n;i++) m=m+w[i][j];

if (min>m) { min=m ;k=j;} //取顶点间的距离之和的最小值。 }//for

35. [题目分析] 本题应用宽度优先遍历求解。若以v0作生成树的根为第１层，则距顶点v0最短路径长度为K的顶点均在第K+1层。可用队列存放顶点，将遍历访问顶点的操作改为入队操作。队列中设头尾指针f和r，用level表示层数。 void bfs_K ( graph g ,int v0 ,K)

//输出无向连通图g（未指定存储结构）中距顶点v0最短路径长度为K的顶点。 {int Q[]; //Q为顶点队列，容量足够大。

int f=0,r=0,t=0; //f和r分别为队头和队尾指针，t指向当前层最后顶点。 int level=0,flag=0; //层数和访问成功标记。 visited[v0]=1; //设v0为根。

Q[++r]=v0; t=r; level=1; //v0入队。 while (f

w=GraphFirstAdj(g,v);

while (w!=0) //w!=0 表示邻接点存在。 {if (visited[w]==0)

{Q[++r]=w; visited[w]=1;//邻接点入队列。

if (level==K+1){ printf(\距顶点v0最短路径为k的顶点%d \if }//if

w=GraphNextAdj(g ,v ,w); }//while(w!=0)

if (f==t) {level++；t=r; }//当前层处理完，修改层数，t指向下一层最后一个顶点 }//while(f

if (flag==0) printf( \图中无距v0顶点最短路径为%d的顶点。\\n\

}//算法结束。

[设法讨论]本题亦可采取另一个算法。由于在生成树中结点的层数等于其双亲层次数加

1，故可设顶点和层次数２个队列，其入队和出队操作同步，其核心语句段如下： QueueInit(Q1) ; QueueInit(Q2); //Q1和Q2是顶点和顶点所在层次数的队列。 visited[v0]=1; //访问数组初始化，置v0被访问标记。 level=1; flag=0; //是否有层次为K的顶点的标志

QueueIn(Q1,v0); QueueIn(Q2,level); //顶点和层数入队列。 while (!empty(Q1) && level<=K+1)

{v=QueueOut(Q1); level=QueueOut(Q2);//顶点和层数出队。 w=GraphFirstAdj(g,v0); while (w!=0) //邻接点存在。 {if (visited[w]==0) if (level==K+1)

{printf(\距离顶点v0最短路径长度为K的顶点是%d\\n\

visited[w]=1; flag=1; QueueIn(Q1 ,w); QueueIn(Q2,level+1); }//if w=GraphNextAdj(g ,v ,w); }//while(w!=0)

}//while(!empty(Q1) && level

if (flag==0) printf( \图中无距v0顶点最短路径为%d的顶点。\\n\36. 对于无环连通图，顶点间均有路径，树的直径是生成树上距根结点最远的两个叶子间的距离，利用深度优先遍历可求出图的直径。

int dfs(Graph g ,vertype parent ,vertype child ,int len)

//深度优先遍历，返回从根到结点child所在的子树的叶结点的最大距离。 {current_len=len; maxlen=len; v=GraphFirstAdj(g ,child); while (v!=0) //邻接点存在。 if (v!=parent)

{len=len+length(g ,child ,c); dfs(g ,child ,v ,len); if (len>maxlen) maxlen=len;

v=GraphNextAdj(g ,child ,v); len=current_len; } //if len=maxlen; return(len);

}//结束dfs。

int Find_Diamenter (Graph g)

//求无向连通图的直径，图的顶点信息为图的编号。

{maxlen1=0; maxlen2=0; //存放目前找到的根到叶结点路径的最大值和次大值。 len=0; ///深度优先生成树根到某叶结点间的距离

w=GraphFirstAdj(g,1); //顶点１为生成树的根。 while (w!=0) //邻接点存在。 {len=length(g ,1 ,w);

if (len>maxlen1) {maxlen2=maxlen1; maxlen1=len;} elseif (len>maxlen2) maxlen2=len;

w=GraphNextAdj(g ,1 ,w);//找顶点1的下一邻接点。 }//while

printf( \无向连通图g的最大直径是%d\\n\return(maxlen1+maxlen2);

本文来源：https://www.bwwdw.com/article/mm4x.html