图的深度优先遍历+732图的广度优先遍历.ppt

1、7.3 图的遍历,回顾其他数据结构的遍历： 顺序表的遍历 单链表的遍历 二叉树、树和森林的遍历 问题： 那么对于图，我们怎样进行遍历呢？ (需要记录访问过顶点的信息，引入visited0n-1) 图的深度优先遍历 图的广度优先遍历 这两个算法是后面拓扑排序、求关键路径算法的基础,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,

2、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,

3、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,

4、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,练习题： 对于下面一个图及其存储结构，写出以v2、v8为起始点的深度优先遍历序列。,例图及其邻接表表示,答案为： 以v2为起始点：v2-v1-v3-v6-v7-v4-v8-v5 v2-v4-v8-v5-v1-v3-v6-v7 以v8为起始点

5、：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为遍历的起点,队列,v1,访问v1,v1,队列,v1,V1入队列,v1,队列,v1,取队头元素,v1,队列,v1,v2,V1的邻接点v2没有被访问过，访问之，且入队列,v1,队列,v1,v2,v2,

6、v1,队列,v1,v2,v2,v3,V1的邻接点v3没有被访问过，访问之，且入队列,v1,队列,v1,v2,v2,v3,v3,v1,队列,v2,v2,v3,v3,v1,队列,v2,v2,v3,v3,v1,队列,v2,v2,v3,v3,v1,队列,v2,v2,v3,v3,V2的邻接点v1已经被访问过不再访问,v1,队列,v2,v2,v3,v3,v4,V2的邻接点v4没有被访问过，访问之，且入队列,v1,队列,v2,v2,v3,v3,v4,v4,v1,队列,v2,v2,v3,v3,v4,v4,v5,V2的邻接点v5没有被访问过，访问之，且入队列,v1,队列,v2,v2,v3,v3,v4,v4,v5

7、,v5,v1,队列,v2,v3,v3,v4,v4,v5,v5,v1,队列,v2,v3,v3,v4,v4,v5,v5,v1,队列,v2,v3,v3,v4,v4,v5,v5,v1,队列,v2,v3,v3,v4,v4,v5,v5,V3的邻接点v1已经被访问过不再访问,v1,队列,v2,v3,v3,v4,v4,v5,v5,v6,V3的邻接点v6没有被访问过，访问之，且入队列,v1,队列,v2,v3,v3,v4,v4,v5,v5,v6,v6,v1,队列,v2,v3,v3,v4,v4,v5,v5,v6,v6,v7,V3的邻接点v7没有被访问过，访问之，且入队列,v1,队列,v2,v3,v3,v4,v4,v

8、5,v5,v6,v6,v7,v7,v1,队列,v2,v3,v4,v4,v5,v5,v6,v6,v7,v7,v1,队列,v2,v3,v4,v4,v5,v5,v6,v6,v7,v7,v1,队列,v2,v3,v4,v4,v5,v5,v6,v6,v7,v7,v1,队列,v2,v3,v4,v4,v5,v5,v6,v6,v7,v7,V4的邻接点v2已经被访问过不再访问,v1,队列,v2,v3,v4,v4,v5,v5,v6,v6,v7,v7,v8,V4的邻接点v8没有被访问过，访问之，且入队列,v1,队列,v2,v3,v4,v4,v5,v5,v6,v6,v7,v7,v8,v8,v1,队列,v2,v3,v4,

9、v5,v5,v6,v6,v7,v7,v8,v8,v1,队列,v2,v3,v4,v5,v5,v6,v6,v7,v7,v8,v8,v1,队列,v2,v3,v4,v5,v5,v6,v6,v7,v7,v8,v8,V5的邻接点v2、v8已经被访问过不再访问,v1,队列,v2,v3,v4,v5,v6,v6,v7,v7,v8,v8,v1,队列,v2,v3,v4,v5,v6,v6,v7,v7,v8,v8,v1,队列,v2,v3,v4,v5,v6,v6,v7,v7,v8,v8,V6的邻接点v3、v7已经被访问过不再访问,v1,队列,v2,v3,v4,v5,v6,v7,v7,v8,v8,v1,队列,v2,v3,v4,v5,v6,v7,v7,v8,v8,v1,队列,v2,v3,v4,v5,v6,v7,v7,v8,v8,V7的邻接点v3、v6已经被访问过不再访问,v1,队列,v2,v3,v4,v5,v6,v7,v8,v8,v1,队列,v2,v3,v4,v5,v6,v7,v8,v8,V8的邻接点v4、v5已经被访问过不再访问,v1,队列,v2,v