教黎 第七章图 程序设计—数据结构 图的遍历算法及其应用 这样，引入数组Ph用来保存当前已搜索的简单路径上的顶点，引入计数器n用来记录 当前该路径上的顶点数。 对DFS算法的修改如下： 1)计数器n的初始化，放在visited的初始化前后： 2)访问顶点时，增加将该顶点序号入数组Path中，计数器nt+:判断是否已获得所求路 径，是则输出结束，否则继续遍历邻接点： 3)某顶点的全部邻接点都访问后，仍未得到简单路径，则回溯，将该顶点置为未访问， 计数器n-一。 2、算法 /体邻接矩阵表示法，粗体字部分为在深度优先遍历上的增加或修改的步骤*/ void Hamilton(MGraph G) for (i=0;i<G.vexnum;i++) visited[i]=FALSE: n=0; for i=0;i<G.vexnum;+) if(!visited[i]DFS(G,i); void DFS(MGraph G,int i) visitedfi]=TRUE: Path[n]=i; n++; if(n=G.vexnum)Print(Path);/体符合条件，输出该简单路径*/ for(j=0;j<G.vexnum;j++) if(G.arcs[i][j].adj&&!visited[j]) DFS(G,j)月 visited[i]FALSE; n--; } 3、思考 1)若图中存在多条符合条件的路径，本算法是输出一条，还是输出全部？ 2)如何修改算法，变成判断是否有包含全部顶点的简单路径？ 3)如何修改算法，输出包含全部顶点的简单路径的条数？ 4)如何修改算法，输出所有的简单回路？ 5)考虑其他图的存储方法对算法的影响： 6)考虑在非递归的深度优先遍历算法上，如何修改使之适应本问题的求解。 7.4.3求距v0的各顶点中最短路径长度最长的一个顶点 1、思路 由于题意强调为最短路径，因此应当考虑BFS的算法应用。本问题的求解转变成：从vO 出发进行BFS,最后一层的顶点距离vO的最短路径长度最长。 由于BF$类似于树的按层次遍历，需要引入队列用来保存本身已访问但其邻接点尚未全部 访问的顶点。BFS遍历中最后一层的顶点一定是最后出队的若干顶点，队列中最后一个出队的 顶点必定是符合题意的顶点。 这样，只需调用BFS的算法，将最后出队的元素返回即可。 2、算法 文档编号 完成时间 完成人张昱 修改时间20026-6 第9页程序设计——数据结构 第七章 图 图的遍历算法及其应用 文档编号 完 成 人 张 昱 完成时间 修改时间 2002-6-6 第 9 页 这样，引入数组 Path 用来保存当前已搜索的简单路径上的顶点，引入计数器 n 用来记录 当前该路径上的顶点数。 对 DFS 算法的修改如下： 1）计数器 n 的初始化，放在 visited 的初始化前后； 2）访问顶点时，增加将该顶点序号入数组 Path 中，计数器 n++；判断是否已获得所求路 径，是则输出结束，否则继续遍历邻接点； 3）某顶点的全部邻接点都访问后，仍未得到简单路径，则回溯，将该顶点置为未访问， 计数器 n--。 2、算法 /* 邻接矩阵表示法, 粗体字部分为在深度优先遍历上的增加或修改的步骤 */ void Hamilton(MGraph G) { for ( i=0; i<G.vexnum; i++ ) visited[i] = FALSE; n = 0; for ( i=0; i<G.vexnum; i++ ) if ( !visited[i] ) DFS (G, i); } void DFS(MGraph G, int i) { visited[i] = TRUE; Path[n] = i; n++; if ( n == G.vexnum ) Print(Path); /* 符合条件，输出该简单路径 */ for( j=0; j<G.vexnum; j++ ) if ( G.arcs[i][j].adj && !visited[j]) DFS( G, j ); visited[i] = FALSE; n--; } 3、思考 1）若图中存在多条符合条件的路径，本算法是输出一条，还是输出全部？ 2）如何修改算法，变成判断是否有包含全部顶点的简单路径？ 3）如何修改算法，输出包含全部顶点的简单路径的条数？ 4）如何修改算法，输出所有的简单回路？ 5）考虑其他图的存储方法对算法的影响； 6）考虑在非递归的深度优先遍历算法上，如何修改使之适应本问题的求解。 7.4.3 求距 v0 的各顶点中最短路径长度最长的一个顶点 1、思路 由于题意强调为最短路径，因此应当考虑 BFS 的算法应用。本问题的求解转变成：从 v0 出发进行 BFS，最后一层的顶点距离 v0 的最短路径长度最长。 由于 BFS 类似于树的按层次遍历，需要引入队列用来保存本身已访问但其邻接点尚未全部 访问的顶点。BFS 遍历中最后一层的顶点一定是最后出队的若干顶点，队列中最后一个出队的 顶点必定是符合题意的顶点。 这样，只需调用 BFS 的算法，将最后出队的元素返回即可。 2、算法