（1） （2） （3） （4） （5） （6）

7.1 已知如图所示的有向图，请给出该图的： 每个顶点的入度、出度； 邻接矩阵； 邻接表； 逆邻接表； 十字链表； 强连通分量。

7.2 已知如图所示的无向图，请给出该图的： (1) 邻接多重表；（要求每个边结点中第一个顶点号小于第二个顶点号，且每个顶点的 各邻接边的链接顺序，为它所邻接到的顶点序号由小到大的顺序。） (2 深度优先遍历该图所得顶点序列和边的序列； (3) 广度优先遍历该图所得顶点序列和边的序列。

7.3 已知如图所示的 AOE 网，试求： (1) 每个事件的最早发生时间和最晚发生时间； (2) 每个活动的最早开始时间和最晚开始时间； (3) 给出关键路径。

7.4 已知如图所示的有向网，试利用 Dijkstra 算法求顶点 1 到其余顶点的最短路径，并给出 算法执行过程中各步的状态。

7.8 试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中，是否存在 由顶点 vi 到顶点 vj 的路径（i≠j）。注意：算法中涉及的图的基本操作必须在此存储结 构上实现。 7.9 同上题要求。试基于图的广度优先搜索策略写一算法。 7.10 试利用栈的基本操作，编写按深度优先策略遍历一个强连通图的非递归形式的算法。 算法中不规定具体的存储结构，而将图 Graph 看成是一种抽象数据类型。 7.11 采用邻接表存储结构， 编写一个判别无向图中任意给定的两个顶点之间是否存在一条长 度为 k 的简单路径（指顶点序列中不含有重现的顶点）的算法。 7.12 下图是带权的有向图 G 的邻接表表示法。从结点 V1 出发，深度遍历图 G 所得结点序 列为（ A ），广度遍历图 G 所得结点序列为（ B ）；G 的一个拓扑序列是（ C ）； 从结点 V1 到结点

一、分别用邻接矩阵和邻接表实现图的深度优先遍历和广度优先遍历。 二、校园导游程序。 用无向网表示你所在学校的校园景点平面图， 图中顶点表示主要景点， 存放景点的编号、 名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。 要求实现以下功能： （1） 查询各景点的相关信息； （2） 查询图中任意两个景点间的最短路径。 （3） 查询图中任意两个景点间的所有路径。 三、编程求解关键路径问题。
7.1 已知如图所示的有向图，请给出该图的： 1 5

（1） （2） （3） （4） （5） （6）

每个顶点的入度、出度； 邻接矩阵； 邻接表； 逆邻接表； 十字链表； 强连通分量。

7.2 已知如图所示的无向图，请给出该图的： （2）深度优先遍历该图所得顶点序列和边的序列； （3）广度优先遍历该图所得顶点序列和边的序列。

【解答】 （2）深度优先搜索 顶点序列：1-2-3-4-5-6 边的序列： （1，2） （2，3） （3，4） （4，5） （5，6）

（2）广度优先搜索 顶点序列：1-2-3-6-5-4 边的序列： （1，2） （1，3） （1，6） （1，5） （5，4）

深度优先搜索树： 注：本题中所求深度优先序列和广度优先序列有多种，以上为其中一种。 7．3 【解答】 源点 终点 最短路径 路径长度 1 2 1，3，2 19 3 1，3 15 4 1，3，2，4 29 5 1，3，5 29 6 1，3，2，4，6 44 7．12 【解答】 （A） 深度遍历：1，2，3，8，4，5，7，6 或 1，2，3，8，5，7，4， （B）