图的深度优先遍历.ppt

7 3图的遍历 回顾其他数据结构的遍历 顺序表的遍历单链表的遍历二叉树的遍历展望 那么对于图 我们怎样进行遍历呢 图的深度优先遍历图的广度优先遍历这两个算法是后面拓扑排序 求关键路径算法的基础 7 3 1 连通图的深度优先遍历 1 深度优先遍历以v开始的连通图 访问v分别深度优先遍历v的各个未被访问的邻接点 算法描述 2 算法演示 例图及其邻接表表示 演示开始 以v1为遍历的起点 v1 v3 v2 v3 v3 v1 v5 v4 v3 v1 v5 v4 v3 v1 v5 v3 v1 v5 v2 v8 v3 v1 v5 v2 v8 v3 v1 v5 v2 v3 v1 v5 v2 v4 v5 v3 v1 v5 v2 v4 v5 v3 v1 v5 v2 v4 v3 v1 v5 v2 v4 v2 v8 v3 v1 v5 v2 v4 v2 v8 v3 v1 v5 v2 v4 v2 v8 v3 v1 v5 v2 v4 v2 v8 v3 v1 v5 v2 v4 v2 v8 v3 v1 v5 v2 v4 v2 v8 v3 v1 v5 v2 v4 v2 v8 v3 v1 v5 v2 v4 v2 v8 v3 v1 v5 v2 v4 v2 v8 v3 v1 v5 v2 v4 v2 v8 v1 v5 v2 v4 v2 v8 v1 v5 v2 v4 v2 v8 v1 v6 v7 v1 v5 v2 v4 v2 v8 v1 v6 v7 v1 v5 v2 v4 v2 v8 v1 v7 v1 v5 v2 v4 v2 v8 v1 v7 v3 v7 v1 v5 v2 v4 v2 v8 v1 v7 v3 v7 v1 v5 v2 v4 v2 v8 v1 v7 v3 v1 v5 v2 v4 v2 v8 v1 v7 v3 v3 v6 v1 v5 v2 v4 v2 v8 v1 v7 v3 v3 v6 v1 v5 v2 v4 v2 v8 v1 v7 v3 v3 v6 v1 v5 v2 v4 v2 v8 v1 v7 v3 v3 v6 v1 v5 v2 v4 v2 v8 v1 v7 v3 v3 v6 v1 v5 v2 v4 v2 v8 v1 v7 v3 v3 v6 v1 v5 v2 v4 v2 v8 v1 v7 v3 v3 v6 v1 v5 v2 v4 v2 v8 v1 v7 v3 v3 v6 v1 v5 v2 v4 v2 v8 v1 v7 v3 v3 v6 演示结束 3 算法实现 从演示过程可以看出 我们必须知道顶点是否已经被访问过 在具体实现时 我们用一个全局数组visited 来记录顶点是否被访问过 如果visited i 的值为True 则顶点vi已经被访问 否则没有被访问 3 算法实现 VoidDFS GraphG intv Visited v True cout v For v的每一个邻接点w If visited w false 如果没有被访问过DFS G w 3 算法实现 当图的存储结构为邻接表时 深度优先算法可以表示如下 boolvisited 100 false voidDFS ALGraphmg intv visited v true 以前未被访问 此处被访问 改变对应的标志为已经访问cout0 w NextAdjVex mg v w 对于v的每一个邻接点进行考察if visited w false 当该结点未被访问时DFS mg w 进行深度优先遍历 练习题 对于下面一个图及其存储结构 写出以v2 v8为起始点的深度优先遍历序列 例图及其邻接表表示 答案为 以v2为起始点 v2 v1 v3 v6 v7 v4 v8 v5以v8为起始点 v8 v4 v2 v1 v3 v6 v7 v5 思考题 若图不是连通图 如何进行深度优先遍历 请建立下图的邻接表结构 并进行深度优先遍历 v1 v2 v3 v4 v5 v6 v7 boolvisited 100