妳來喚醒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分）】 第一.选择题 1.A 10.2BDE 19.AB 28.D 2.B 11.B 20.B 29.B 3.A 12.1B 21.1C 4.B 12.2B 21.2A 5.D 12.3D 21.3B 32.B 6.1B 13.B 21.4A 7章 图
6.2D 14.C 22.A 7.1B 15.C 23.A 7.2C 16.D 24.D 8.A 17.D 25.A 9.A 18.1C 10.1C 18.2C 26.A 27.B 30.A 31.C 二.判断题 1.√ 2. × 13.14.3.× 4.× 5.× 6.√ 7.× 8.× 9.× 10.× 15.16.17.18.19.20.21.22.11.√ 23.12.× 24.× √ 25.× 37.× 49.× × 26.√ 38.× × 27.× 39.× × 28.√ 40.× √ 29.× 41.√ × 30.× 42.× × 31.√ 43.× × 32.√ 44.√ × 33.× 45.× × 34.× 46.× × 35.× 47.× 36.√ 48. √ 部分答案解释如下。
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
A C E D B C D F I B K I J K E 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 。 1 9 8 4 7 5 6 （3）拓扑序列K1，K2，K3，K4，K5，K6，K8，K9，K7 K2，K1，K3，K4，K5，K6，K8，K9，K7
规则：开始结点为K1或K2，之后，若遇多个入
度为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）个顶点和指向各顶点第一邻接点的指针，其顶点的邻接点的链式存储结构是根据顶点的邻接点的实际设计的。这种结构适合查找顶点及邻接点的信息，查顶点的度，增加或删除顶点和边（弧）也很方便，但因指针多占用了存储空间，另外，某两顶点间是否有边（弧）也不如邻接矩阵那么清楚。对有向图的邻接表，查顶点出度容易，而查顶点入度却困难，要遍历整个邻接表。要想查入度象查出度那样容易，就要建立逆邻接表。无向图邻接表中边结点是边数的二倍也增加了存储量。
十字链表是有向图的另一种存储结构，将邻接表和逆邻接表结合到一起，弧结点也增加了信息（至少弧尾，弧头顶点在向量中的下标及从弧尾顶点发出及再入到弧头顶点的下一条弧的四个信息）。查询顶点的出度、入度、邻接点等信息非常方便。
