敦案 第七章图 程序设计—数据结构 图的遍历算法及其应用 7.4遍历算法的应用 7.4.1应用问题概述 图的深度优先遍历： 1、求一条包含图中所有顶点的简单路径（简单回路） 2、判断图中是否存在环 3、求图中通过给定顶点Vk的简单回路 4、判断是否存在从顶点到顶点的路径 5、判别v0和v1之间是否存在一条长度为k的路径 图的广度优先遍历： 1、判断是否存在从顶点到顶点的路径 2、求距V0的各顶点中最短路径长度最长的一个顶点。 3、求v0和v1之间的最短路径 4、在顶点子集U中找出距离顶点v0最近的顶点 5、求顶点v0到其余每个顶点的最短路径 6、求距离顶点v0的最短路径长度为k的所有顶点 7.4.2求一条包含图中所有顶点的简单路径 1、思路 对于任意的有向图或无向图G,并不一定都能找到符合题意的简单路径。这样的简单路径 要求包含G.vexnum个顶点，且互不相同。它的查找可以基于深度优先遍历。 在一个存在包含全部顶点的简单路径的图中，以下因素会影响该简单路径是否能顺利地查 到： l)起点的选择：如图(a),其符合题意的一条简单 路径如图(b)。若起点为1，则不能找到符合题 ④ 意的简单路径： 7 2)顶点的邻接点次序：进一步考察图(a),即使以 (6 2为起点，但是2的邻接点选择的是1，而不是 (a) (b) 5,此时也不能找到符合题意的解。 在基于DFS的查找算法中，由于起点和邻接点的选取是与顶点和邻接点的存储次序以及算 法的搜索次序有关，不可能依据特定的图给出特定的解决算法。因此，在整个搜索中应允许有 查找失败，此时可采取回湖到上一层的方法，继续查找其他路径。 文档编号 完成时间 完成人张昱 修改时间20026-6 第8页程序设计——数据结构 第七章 图 图的遍历算法及其应用 文档编号 完 成 人 张 昱 完成时间 修改时间 2002-6-6 第 8 页 7.4 遍历算法的应用 7.4.1 应用问题概述 图的深度优先遍历： 1、 求一条包含图中所有顶点的简单路径(简单回路) 2、 判断图中是否存在环 3、 求图中通过给定顶点 vk的简单回路 4、 判断是否存在从顶点 vi到顶点 vj的路径 5、 判别 v0 和 v1 之间是否存在一条长度为 k 的路径 图的广度优先遍历： 1、 判断是否存在从顶点 vi到顶点 vj的路径 2、 求距 v0 的各顶点中最短路径长度最长的一个顶点。 3、 求 v0 和 v1 之间的最短路径. 4、 在顶点子集 U 中找出距离顶点 v0 最近的顶点 5、 求顶点 v0 到其余每个顶点的最短路径 6、 求距离顶点 v0 的最短路径长度为 k 的所有顶点 7.4.2 求一条包含图中所有顶点的简单路径 1、思路 对于任意的有向图或无向图 G，并不一定都能找到符合题意的简单路径。这样的简单路径 要求包含 G.vexnum 个顶点，且互不相同。它的查找可以基于深度优先遍历。 在一个存在包含全部顶点的简单路径的图中，以下因素会影响该简单路径是否能顺利地查 到： 1）起点的选择：如图(a)，其符合题意的一条简单 路径如图(b)。若起点为 1，则不能找到符合题 意的简单路径； 2）顶点的邻接点次序：进一步考察图(a)，即使以 2 为起点，但是 2 的邻接点选择的是 1，而不是 5，此时也不能找到符合题意的解。 在基于 DFS 的查找算法中，由于起点和邻接点的选取是与顶点和邻接点的存储次序以及算 法的搜索次序有关，不可能依据特定的图给出特定的解决算法。因此，在整个搜索中应允许有 查找失败，此时可采取回溯到上一层的方法，继续查找其他路径。 1 2 3 4 5 6 7 1 2 3 4 5 6 7 (a) (b)