1、7.3 图的遍历回顾其他数据结构的遍历：顺序表的遍历 单链表的遍历 二叉树、树和森林的遍历问题：那么对于图，我们怎样进行遍历呢？(需要记录访问过顶点的信息，引入visited0n-1)图的深度优先遍历 图的广度优先遍历这两个算法是后面拓扑排序、求关键路径算法的基础7.3.1.连通图的深度优先遍历u 类似于树的先根遍历，是其推广1.深度优先遍历以v开始的连通图 访问v 分别深度优先遍历v的各个未被访问的邻接点算法描述算法描述:2.算法演示01 v12 v23 V34 V45 v56 v67 v78 v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1v2v3v4v5v
2、6v7v8例图及其邻接表表示演示开始，以v1为遍历的起点01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v101v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v101v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1v3v201v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1v3,v201v12v23
3、V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1v3,v2v1v5v401v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1v3,v2v1v5v401v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1v3,v2v1v5,v401v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1v3,v2v1v5,v4v2v801
4、v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1v3,v2v1v5,v4v2v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1v3,v2v1v5,v4v2,v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1v3,v2v1v5,v4v2,v8v4v501v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v
5、6v4v5,v1v3,v2v1v5,v4v2,v8v4v501v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1v3,v2v1v5,v4v2,v8v4,v501v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1v3,v2v1v5,v4v2,v8v4,v5v2v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1v3,v2v1v5,v4v2,v8v4,v5v2v801v12
6、v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1v3,v2v1v5,v4v2,v8v4,v5v2v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1v3,v2v1v5,v4v2,v8v4,v5v2v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1v3,v2v1v5,v4v2,v8v4,v5v2v801v12v23V34V45v56v67v78v8v2v3v1v4v5
7、v1v6v7v2v8v2v8v3v7v3v6v4v5,v1v3,v2v1v5,v4v2,v8v4,v5v2v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1v3,v2v1v5,v4v2,v8v4,v5v2v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1v3,v2v1v5,v4v2,v8v4,v5v2v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1v
8、3,v2v1v5,v4v2,v8v4,v5v2v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1v3,v2v1v5,v4v2,v8v4,v5v2v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1,v2v1v5,v4v2,v8v4,v5v2v8,v301v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1,v2v1v5,v4v2,v8v4,v5v2v8,v3v1v
9、6v701v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1,v2v1v5,v4v2,v8v4,v5v2v8,v3v1v6v701v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1,v2v1v5,v4v2,v8v4,v5v2v8,v3v1v7,v601v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1,v2v1v5,v4v2,v8v4,v5v2v8,v3v1v7,v6v3v7
10、01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1,v2v1v5,v4v2,v8v4,v5v2v8,v3v1v7,v6v3v701v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1,v2v1v5,v4v2,v8v4,v5v2v8,v3v1v7,v6v3,v701v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1,v2v1v5,v4v2,v8v4,v5v2v8,v3v1v7
11、,v6v3,v7v3v601v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1,v2v1v5,v4v2,v8v4,v5v2v8,v3v1v7,v6v3,v7v3v601v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1,v2v1v5,v4v2,v8v4,v5v2v8,v3v1v7,v6v3,v7v3v601v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1,v2v1v5,v4
12、v2,v8v4,v5v2v8,v3v1v7,v6v3,v7v3v601v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1,v2v1v5,v4v2,v8v4,v5v2v8,v3v1v7,v6v3,v7v3v601v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1,v2v1v5,v4v2,v8v4,v5v2v8,v3v1v7,v6v3,v7v3v601v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7
13、v3v6v4v5,v1,v2v1v5,v4v2,v8v4,v5v2v8,v3v1v7,v6v3,v7v3v601v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1,v2v1v5,v4v2,v8v4,v5v2v8,v3v1v7,v6v3,v7v3v601v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1,v2v1v5,v4v2,v8v4,v5v2v8,v3v1v7,v6v3,v7v3v6练习题：对于下面一个图及其存储结构，写出以v2、v8为起始点的深
14、度优先遍历序列。01 v12 v23 V34 V45 v56 v67 v78 v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1v2v3v4v5v6v7v8例图及其邻接表表示答案为：以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.连通图的广度优先遍历u 类似于树的按层次遍历，是其推广1.广度优先遍历以x开始的连通图 访问X，且x入队列 若队列不空，重复以下步骤 取队头元素并放入缓
15、存v中 考察v的各个邻接点，若未访问，则先访问，然后放在队列尾部 返回步骤算法描述算法描述:2.算法演示01 v12 v23 V34 V45 v56 v67 v78 v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1v2v3v4v5v6v7v8例图及其邻接表表示演示开始，以v1为遍历的起点01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5队列队列v1访问v101v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v1
16、V1入队列01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v1取队头元素01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v1v2V1的邻接点v2没有被访问过，访问之，且入队列01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v1v2v201v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v
17、3v6v4v5v1队列队列v1v2v2v3V1的邻接点v3没有被访问过，访问之，且入队列01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v1v2v2v3v301v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v2v3v301v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v2v3v301v12v23V34V45v56v67v78v8v2v3
18、v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v2v3v301v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v2v3v3V2的邻接点v1已经被访问过不再访问01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v2v3v3v4V2的邻接点v4没有被访问过，访问之，且入队列01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5
19、v1队列队列v2v2v3v3v4v401v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v2v3v3v4v4v5V2的邻接点v5没有被访问过，访问之，且入队列01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v2v3v3v4v4v5v501v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v3v4v4v5v501v12v23V34V45
20、v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v3v4v4v5v501v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v3v4v4v5v501v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v3v4v4v5v5V3的邻接点v1已经被访问过不再访问01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7
21、v3v6v4v5v1队列队列v2v3v3v4v4v5v5v6V3的邻接点v6没有被访问过，访问之，且入队列01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v3v4v4v5v5v6v601v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v3v4v4v5v5v6v6v7V3的邻接点v7没有被访问过，访问之，且入队列01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v
22、7v3v6v4v5v1队列队列v2v3v3v4v4v5v5v6v6v7v701v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v4v5v5v6v6v7v701v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v4v5v5v6v6v7v701v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v4v5v5v6v6v7v701
23、v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v4v5v5v6v6v7v7V4的邻接点v2已经被访问过不再访问01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v4v5v5v6v6v7v7v8V4的邻接点v8没有被访问过，访问之，且入队列01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v4v5v5v6v6v7
24、v7v8v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v5v5v6v6v7v7v8v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v5v5v6v6v7v7v8v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v5v5v6v6v7v7v8v8V5的邻接点v2、v8已经被访问过不再访问01v12v
25、23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v5v6v6v7v7v8v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v5v6v6v7v7v8v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v5v6v6v7v7v8v8V6的邻接点v3、v7已经被访问过不再访问01v12v23V34V45v56v67v78v
26、8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v5v6v7v7v8v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v5v6v7v7v8v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v5v6v7v7v8v8V7的邻接点v3、v6已经被访问过不再访问01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v
27、8v3v7v3v6v4v5v1队列队列v2v3v4v5v6v7v8v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v5v6v7v8v8V8的邻接点v4、v5已经被访问过不再访问01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v5v6v7v8队列为空，算法结束 练习题：对于下面一个图及其存储结构，写出以v2、v8为起始点的广度优先遍历序列。01 v12 v23 V34 V45 v56 v67 v78 v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1v2v3v4v5v6v7v8例图及其邻接表表示答案如下：以v2为起始点：v2-v1-v4-v5-v3-v8-v6-v7 以v8为起始点：v8-v4-v5-v2-v1-v3-v6-v7
