发布时间 : 星期二 文章第七章 图更新完毕开始阅读ff5e30e19b89680203d825c8
要求：（1）．对所用的辅助数据结构，邻接表结构给以必要的说明；（6分）
（2）．写出算法描述。(C,类-Pascal,类-C均可)（14分） 【南京理工大学 1996 四、1 （20分）】
类似本题的另外叙述有： （1）写出求从某个源点到其余各顶点最短路径的Dijkstra算法。要求说明主要的数据结构及其作
用，最后针对所给有向图，利用该算法，求V0到各顶点的最短距离和路线，即填写下表：
终点 V1 V2 V3 V4 V5 Vj V2 从V0到到各终点的dist的值和最短距离和路线 V3 50V010V15V220 1040V530V420V3 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 c 4 3 10 4 4 2 2 a 1 b 2 3 e 6 6 7 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分）】