（1）．请回答什么是G的最小生成树；
（2）．G为下图所示,请找出G的所有最小生成树。【北方交通大学 1993 二 （12分）】 29．试写出用克鲁斯卡尔（Kruskal）算法构造下图的一棵最小支撑（或生成）树的过程。
5
21 7818 21 2 5 6 12 83 23 85 3 8 647 4 15 3325 7 10 24 6 7420 3
第29图
46657【吉林大学 2000 一、3 (3分)】
30.求出下图的最小生成树。【合肥工业大学 1999 四、2 （5分）】 第30题图
31．一带权无向图的邻接矩阵如下图 ，试画出它的一棵最小生成树。
【浙江大学 1994 五 (8分)】 第32题图
32．请看下边的无向加权图。 （1）．写出它的邻接矩阵（ 5分） （2）．按Prim算法求其最小生成树，并给出构造最小生成树过程中辅助数组的各分量值（15分）
辅助数组内各分量值：【华北计算机系统工程研究所 1999 四 （20分）】
Y Closedge Vex Lowcost Vex Lowcost Vex Lowcost Vex Lowcost 2 3 4 5 6 7 8 U V.-U Vex Lowcost Vex Lowcost Vex Lowcost Vex Lowcost 33．已知世界六大城市为:北京(Pe)、纽约(N)、巴黎(Pa)、 伦敦(L) 、 东京(T) 、 墨西哥(M),下表给定了这六大城市之间的交通里程:
世界六大城市交通里程表(单位:百公里)
PE N PA L T M 1 2 5 1 3 8 （1）．画出这六大城市的交通网络图; （2）．画出该图的邻接表表示法; （3）．画出该图按权值递增的顺序来构造的最小(代价)生成树. 【上海海运学院1995 六（9分） 1999 五 （14分）】
PE 109 82 81 21 124 N 109 58 55 108 32 PA 82 58 3 97 92 L 81 55 3 95 89 T 21 108 97 95 113 M 124 32 92 89 113
1 4 3 2 4 6 ：每行三个数表示一条2 3 2 34．已知顶点1-6和输入边与权值的序列（如右图所示）
3 4 4 边 3 5 1 的两个端点和其权值，共11行。请你：
．采用邻接多重表表示该无向网，用类PASCAL语言描述该数据结构，画出3 6 10 （1）
4 5 7 存
4 6 11 储结构示意图，要求符合在边结点链表头部插入的算法和输入序列的次序。
．分别写出从顶点1出发的深度优先和广度优先遍历顶点序列，以及相应5 6 15 （2）的
生成树。
（3）．按prim算法列表计算，从顶点1始求最小生成树，并图示该树。 【北京工业大学 1999 四(20分)】
35．下图表示一个地区的通讯网，边表示城市间的通讯线路，边上的权表示架设线路花费的代价，如何选择能沟通每个城市且总代价最省的n-1条线路，画出所有可能的选择。【东北大学2000一、4(4分)】
161221191143351861466355 c 4 e a 6 7 h 3 2 f 1 b 5 3 d 8
第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分)】
37．有一图的邻接矩阵如下，试给出用弗洛伊德算法求各点间最短距离的矩阵序列A1，A2，A，A。 ?0????5?3 A=?20???10????6?4??0?
3
4
【北京邮电大学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题图
230338542? 4V4
110618? 5V5
6V6?
39．用最短路径算法，求如下图中a到z的最短通路。【西南财经大学 1999 四】 40．已知一有向网的邻接矩阵如下，如需在其中一个结点建立娱乐中心，要求该结点距其它各结点的最长往返路程最短，相同条件下总的往返路程越短越好，问娱乐中心应选址何处？给出解题过程。
V1?0?V2??V3?4?V41?V5???V6??20??1??30??2?2?0?5??410?3?????????3??0? 第41题图
【北京邮电大学 2002 四、1 （10分）】
41．求出下图中顶点1到其余各顶点的最短路径。【厦门大学 2002 八、2 （5分）】 42．试利用Dijkstra算法求下图中从顶点a到其他个顶点间的最短路径，写出执行算法过程中各步的状态。
【东南大学 2000 四（10分）】
43．对于如下的加权有向图，给出算法Dijkstra产生的最短路径的支撑树，设顶点A为源
点，并写出生成过程。【吉林大学 1999 一、2 (4分)】
3A212015C45
BE 2035D30204015
第43题图
第42题图
44．已知图的邻接矩阵为： V1 V2 V3 V4 V5 V6 V7 V8 V9 V10 V1 V2 V3 V4 V5 V6 V7 V8 V9 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 1 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为终点，给出所有事件允许发生的最早时间和最晚时间，并给出关键路径； （4）．求V1结点到各点的最短距离。【北京邮电大学 2000 五 （15分）】
3 10
V1 V3 V5 V7 3 2 1
2 1 7 4 8 6 3 5 第46题图
3 V8 V6 V4 V2 5 4 6
第45题图
46．（1）．对于有向无环图，叙述求拓扑有序序列的步骤； （2）．对于以下的图，写出它的四个不同的拓扑有序序列。【南开大学 1998 二 (12分)】 47．有向图的拓扑排序能否用图的深度搜索模式来查找?若能，请简述方法，若不能，请简述原因
【西北大学 2000 二、8 (5分)】
48．下图是带权的有向图G的邻接表表示法，求：
（1）．以结点V1出发深度遍历图G所得的结点序列；
（2）．以结点V1出发广度遍历图G所得的结点序列； （3）．从结点V1到结点V8的最短路径； （4）．从结点V1到结点V8的关键路径。
【青岛海洋大学 1999 四（10分）】
49．对有五个结点{ A,B, C, D, E}的图的邻接矩阵，
?0???????????10006010?30?0????2005010?????????0??
（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 所需 10 50 15 300 15 120 M N 15 30