第七章--图的深度优先遍历.ppt

主讲教师：李晓娜 《数据结构》 课程 图的遍历 目录 CONTENTS 图的遍历的定义 深度优先遍历的基本思想 深度优先遍历的实现过程 图的遍历的定义 1 从图的任意指定顶点出发，依照某种规则去访问图中所有顶 点，且每个顶点仅被访问一次，这一过程叫做图的遍历。 遍历实质：找每个顶点的邻接点的过程。 图的遍历 图的遍历的定义 1 图没有“自然”的首结点 图的任意一个顶点都可作为第一个被访问的首结点 非连通图中，从一个顶点出发，只能够访问它所在的连通分量上的所有顶点 需考虑如何选取下一个出发点以访问其余连通分量 图中若有回路存在，则一个顶点被访问之后，有可能沿回路又回到该顶点 区分已访问顶点、未访问顶点 有哪些信誉好的足球投注网站路径 图的特殊性 深度优先遍历 广度优先遍历 DFS基本思想 2 深度优先遍历（Depth_First Search，DFS）是指按照深度方向有哪些信誉好的足球投注网站 ，它类似于树的先根遍历。 (1) 从图中某个顶点Vi出发，首先访问Vi。 (2) 选择一个与刚访问过的顶点Vi相邻接且未访问过的顶点Vj，并访问该顶点。以该顶点为新顶点，重复步骤(2)，直到当前顶点的邻接顶点都已被访问为止。 (3) 返回前一个访问过的且仍有未访问的邻接点的顶点，找出并访问该顶点的下一个未被访问的邻接点，然后重复步骤(2)。 深度优先遍历 DFS基本思想 2 * * v5 v3 v2 v7 v8 v0 v6 v1 （a） 例：深度优先遍历 v4 V0 V1 V2 V3 V6 V8 V7 V5 V4 V0 V1 V2 V3 V4 V5 V6 V7 V8 由此，得到顶点访问序列为： v0-v1-v2-v3-v4-v5-v6-v7-v8 思考：还能生成其他序列吗？ 如何判别顶点V的邻接点是否被访问？ DFS基本思想 2 解决办法：为每个顶点设立一个“访问标志”位。可设置一个辅助数组 visited [n]，用来标记每个被访问过的顶点。 初始状态，将图中每个顶点的访问标志设为 0,之后有哪些信誉好的足球投注网站图中每个顶点，如果未被访问，就立即改 visited [i]为1，防止它被多次访问。并且以该顶点为新的起始点，继续进行深度 优先遍历，否则继续检查下一个未被访问的顶点。 DFS的实现过程 3 1 2 3 4 5 6 1 0 0 0 0 0 0 2 0 0 0 0 0 0 3 0 0 0 0 0 0 4 0 0 0 0 0 0 5 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 0 1 0 0 0 0 1 1 0 0 0 0 1 1 1 0 0 0 1 1 1 0 1 0 1 1 1 1 1 0 1 1 1 1 1 1 DFS 结果 辅助数组 visited [n ] v2→v1→v3→v5→v4→v6 1 2 3 4 5 6 1 0 1 1 1 0 0 2 1 0 0 0 1 0 3 1 0 0 0 1 0 4 1 0 0 0 0 1 5 0 1 1 0 0 0 6 0 0 0 1 0 0 起点 图的邻接矩阵 谢谢学习 主讲教师：李晓娜 * *