内容发布更新时间 : 2024/11/6 0:45:08星期一 下面是文章的全部内容请认真阅读。
7.8 7.9
已知如图7.30所示的有向网，试利用Dijkstra算法求顶点1到其余顶点的最短路径，并给出算法执行过程中各步的状态。
7.5
试在邻接矩阵存储结构上实现图的基本操作：InsertVertex(G,v); InsertArc(G, v, w); DeleteVertex(G,v)和DeleteArc(G, v, w)。
7.6 7.7
试对邻接表存储结构重做题6。
试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中，是否存在由顶点vi到顶点vj的路径（i≠j）。注意：算法中涉及的图的基本操作必须在此存储结构上实现。
7.8 7.9
同上题要求。试基于图的广度优先搜索策略写一算法。
试利用栈的基本操作，编写按深度优先策略遍历一个强连通图的、非递归形式的算法。算法中不规定具体的存储结构，而将图Graph看成是一种抽象数据类型。
7.10
采用邻接表存储结构，编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径（指顶点序列中不含有重现的顶点）的算法。
[提示]：利用深度搜索，增设一个深度参数，深度超过k 则停止对该结点的搜索。 7.11
下图是带权的有向图G的邻接表表示法。从结点V1出发，深度遍历图G所得结点序列为（ A ），广度遍历图G所得结点序列为（ B ）；G的一个拓扑序列是（ C ）；从结点V1到结点V8的最短路径为（ D ）；从结点V1到结点V8的关键路径为（ E ）。
其中A、B、C的选择有： ① V1,V2,V3,V4,V5,V6,V7,V8 ② V1,V2,V4,V6,V5,V3,V7,V8 ③ V1,V2,V4,V6,V3,V5,V7,V8 ④ V1,V2,V4,V6,V7,V3,V5,V8 ⑤ V1,V2,V3,V8,V4,V5,V6,V7 ⑥ V1,V2,V3,V8,V4,V5,V7,V6 ⑦ V1,V2,V3,V8,V5,V7,V4,V6 D、E的选择有： ① V1,V2,V4,V5,V3,V8 ② V1,V6,V5,V3,V8 ③ V1,V6,V7,V8 ④ V1,V2,V5,V7,V8
0 v1 v2 v3 v4 v5 v6 v7 v8 ∧ 1 6 2 43 3 1 4 6 5 50 ∧ 3 11 ∧ 1 2 7 8 ∧ 4 12 ∧ 2 38 4 1 7 20 ∧ 3 4
6 24 ∧ 6 12 ∧ 5 6 7 题12图
7.13 二叉树的层次遍历。
实习题
1． 分别用邻接矩阵和邻接表实现图的深度优先遍历和广度优先遍历。 2． 校园导游程序。
用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。
要求实现以下功能： （1） 查询各景点的相关信息；
（2） 查询图中任意两个景点间的最短路径。 （3） 查询图中任意两个景点间的所有路径。 3． 编程求解关键路径问题。
补充题
1．将图7.31所示的有向网改为无向网，并要求：
（1）用普里姆算法从顶点9开始，手工构造最小生成树。（最小代价连通网） （2）用克鲁斯卡尔算法手工构造最小生成树。
（注： 可将结点看成电脑，将权值看成电缆代价；也可将结点看成城市，将权值看成电缆代价；还可将结点看成城市，将权值看成修路代价；）
2．
将图7.31所示的AOE-网改为AOV-网（去掉权值即可），并给出一个拓扑序列。（要求优先输出编号小的顶点）。
5 1 3 4 3 4 6 3 1 2 3 4 4 7 5 5 6 4 0 6 2 8 2 9
图7.31 题7.3 用图
参考题
1．已知有向图，试基于图的深度优先搜索策略写一算法，求顶点vi到顶点vj的一条简单路径（i≠j）。
[提示]：有向图可用邻接表存储，并在表结点中增加一个prior域。
第七章答案
7.1已知如图所示的有向图，请给出该图的：
（1） 每个顶点的入度、出度； （2） 邻接矩阵； （3） 邻接表； （4） 逆邻接表； （5） 十字链表；
（6） 强连通分量。
题1图 3 2 4 6 1 5
【解答】
（1）顶点 入度 出度 1 3 0 2 2 2 3 1 2 4 1 3 5 2 1 6 2 3
7.2 已知如图所示的无向图，请给出该图的： （2）深度优先遍历该图所得顶点序列和边的序列； （3）广度优先遍历该图所得顶点序列和边的序列。 【解答】
（2）深度优先搜索 顶点序列：1-2-3-4-5-6
边的序列：（1，2）（2，3）（3，4）（4，5）（5，6） 深度优先搜索树： （3）广度优先搜索 顶点序列：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 【解答】
（1）深度遍历：1，2，3，8，4，5，7，6或1，2，3，8，5，7，4， （2）广度遍历：1，2，4，6，3，5，7，8 （3）拓扑序列：1，2，4，6，5，3，7，8