[2018年最新整理]1图的深度优先遍历+2图的广度优先遍历.ppt

7.3 图的遍历 回顾其他数据结构的遍历： 顺序表的遍历 单链表的遍历 二叉树、树和森林的遍历 问题： 那么对于图，我们怎样进行遍历呢？ (需要记录访问过顶点的信息，引入visited[0…n-1]) 图的深度优先遍历 图的广度优先遍历 这两个算法是后面拓扑排序、求关键路径算法的基础 7.3.1.连通图的深度优先遍历 类似于树的先根遍历，是其推广 1.深度优先遍历以v开始的连通图 访问v 分别深度优先遍历v的各个未被访问的邻接点 2.算法演示 演示开始，以v1为遍历的起点 练习题： 对于下面一个图及其存储结构，写出以v2、v8为起始点的深度优先遍历序列。 答案为： 以v2为起始点：v2-v1-v3-v6-v7-v4-v8-v5 v2-v4-v8-v5-v1-v3-v6-v7 …… 以v8为起始点：v8-v4-v2-v1-v3-v6-v7-v5 v8-v5-v2-v1-v3-v6-v7-v4 …… 7.3.2.连通图的广度优先遍历 类似于树的按层次遍历，是其推广 1.广度优先遍历以x开始的连通图 访问X，且x入队列 若队列不空，重复以下步骤 取队头元素并放入缓存v中 考察v的各个邻接点，若未访问，则先访问，然后放在队列尾部 返回步骤② 2.算法演示 演示开始，以v1为遍历的起点 练习题： 对于下面一个图及其存储结构，写出以v2、v8为起始点的广度优先遍历序列。 答案如下： 以v2为起始点：v2-v1-v4-v5-v3-v8-v6-v7 …… 以v8为起始点：v8-v4-v5-v2-v1-v3-v6-v7 …… v8 8 v7 7 v6 6 v5 5 V4 4 V3 3 v2 2 v1 1 0 v2 v3 v1 v4 v5 v1 v6 v7 v2 v8 v2 v8 v3 v7 v3 v6 v4 v5 v1 队列 v2 v2 v3 v3 V2的邻接点v1已经被访问过不再访问 v8 8 v7 7 v6 6 v5 5 V4 4 V3 3 v2 2 v1 1 0 v2 v3 v1 v4 v5 v1 v6 v7 v2 v8 v2 v8 v3 v7 v3 v6 v4 v5 v1 队列 v2 v2 v3 v3 v4 V2的邻接点v4没有被访问过，访问之，且入队列 v8 8 v7 7 v6 6 v5 5 V4 4 V3 3 v2 2 v1 1 0 v2 v3 v1 v4 v5 v1 v6 v7 v2 v8 v2 v8 v3 v7 v3 v6 v4 v5 v1 队列 v2 v2 v3 v3 v4 v4 v8 8 v7 7 v6 6 v5 5 V4 4 V3 3 v2 2 v1 1 0 v2 v3 v1 v4 v5 v1 v6 v7 v2 v8 v2 v8 v3 v7 v3 v6 v4 v5 v1 队列 v2 v2 v3 v3 v4 v4 v5 V2的邻接点v5没有被访问过，访问之，且入队列 v8 8 v7 7 v6 6 v5 5 V4 4 V3 3 v2 2 v1 1 0 v2 v3 v1 v4 v5 v1 v6 v7 v2 v8 v2 v8 v3 v7 v3 v6 v4 v5 v1 队列 v2 v2 v3 v3 v4 v4 v5 v5 v8 8 v7 7 v6 6 v5 5 V4 4 V3 3 v2 2 v1 1 0 v2 v3 v1 v4 v5 v1 v6 v7 v2 v8 v2 v8 v3 v7 v3 v6 v4 v5 v1 队列 v2 v3 v3 v4 v4 v5 v5 v8 8 v7 7 v6 6 v5 5 V4 4 V3 3 v2 2 v1 1 0 v2 v3 v1 v4 v5 v1 v6 v7 v2 v8 v2 v8 v3 v7 v3 v6 v4 v5 v1 队列 v2 v3 v3 v4 v4 v5 v5 v8 8 v7 7 v6 6 v5 5 V4 4 V3 3 v2 2 v1 1 0 v2 v3 v1 v4 v5 v1 v6 v7 v2 v8 v2 v8 v3 v7 v3 v6 v4 v5 v1 队列 v2 v3 v3 v4 v4 v5 v5 v8 8 v7 7 v6 6 v5 5 V4 4 V3 3 v2 2 v1 1 0 v2 v3 v1 v4 v5 v1 v6 v7 v2 v8 v2 v8 v3 v7 v3 v6 v4 v5 v1 队列 v2 v3 v3 v4 v4 v5 v5 V3的邻接点v1已经