7.3.1图的深度优先遍历+7.3.2图的广度优先遍历

数据结构

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

数据结构

7.3.1.连通图的深度优先遍历 类似于树的先根遍历，是其推广

数据结构

算法描述:

1.深度优先遍历以v开始的连通图① 访问v ② 分别深度优先遍历v的各个未被 访问的邻接点

数据结构

2.算法演示

数据结构

例图及其邻接表表示

01 v1 v2 v3

v1

2 v2v3

v1v1

v4v6

v5v7

v2

3 V3 4 V4

v2v2

v8v8

v4

v5

v6

v7

5 v5 6 v6 7 v7 8 v8

v8

v3v3

v7v6

v4

v5

数据结构

演示开始，以v1为遍历的起点

数据结构

0v1

1 v1

v2

v3

2 v2 3 V3 4 V45 v5 6 v6 7 v7 8 v8

v1v1

v4v6

v5v7

v2v2

v8v8

v3v3

v7v6

v4

v5

数据结构

0v1 ,

1 v1

v2

v3

2 v2 3 V3 4 V45 v5 6 v6 7 v7 8 v8

v1v1

v4v6

v5v7

v2v2

v8v8

v3v3

v7v6

v4

v5

数据结构

0v1 ,

1 v1

v2

v3

2 v2 3 V3 4 V45 v5 6 v6 7 v7 8 v8

v1v1

v4v6

v5v7

v2

v3

v2v2

v8v8

v3v3

v7v6

v4

v5

数据结构

0v1 ,

1 v1

v2

v3

2 v2 3 V3 4 V45 v5 6 v6 7 v7 8 v8

v1v1

v4v6

v5v7

v2 ,

v3

v2v2

v8v8

v3v3

v7v6

v4

v5

数据结构

0v1 ,

1 v1

v2

v3

2 v2 3 V3 4 V45 v5 6 v6 7 v7 8 v8

v1v1

v4v6

v5v7

v2 ,

v3

v1

v4

v5

v2v2

v8v8

v3v3

v7v6

v4

v5

数据结构

0v1 ,

1 v1

v2

v3

2 v2 3 V3 4 V45 v5 6 v6 7 v7 8 v8

v1v1

v4v6

v5v7

v2 ,

v3

v1

v4

v5

v2v2

v8v8

v3v3

v7v6

v4

v5

数据结构

0v1 ,

1 v1

v2

v3

2 v2 3 V3 4 V45 v5 6 v6 7 v7 8 v8

v1v1

v4v6

v5v7

v2 ,

v3

v1

v4 ,

v5

v2v2

v8v8

v3v3

v7v6

v4

v5

数据结构

0v1 ,

1 v1

v2

v3

2 v2 3 V3 4 V45 v5 6 v6 7 v7 8 v8

v1v1

v4v6

v5v7

v2 ,

v3

v1

v4 ,

v5

v2v2

v8v2

v8

v8

v3v3

v7v6

v4

v5

数据结构

0v1 ,

1 v1

v2

v3

2 v2 3 V3 4 V45 v5 6 v6 7 v7 8 v8

v1v1

v4v6

v5v7

v2 ,

v3

v1

v4 ,

v5

v2v2

v8v2

v8

v8

v3v3

v7v6

v4

v5

数据结构

0v1 ,

1 v1

v2

v3

2 v2 3 V3 4 V45 v5 6 v6 7 v7 8 v8

v1v1

v4v6

v5v7

v2 ,

v3

v1

v4 ,

v5

v2v2

v8v2

v8

v8 ,

v3v3

v7v6

v4

v5

数据结构

0v1 ,

1 v1

v2

v3

2 v2 3 V3 4 V45 v5 6 v6 7 v7 8 v8

v1v1

v4v6

v5v7

v2 ,

v3

v1

v4 ,

v5

v2v2

v8v2

v8

v8 ,

v3v3

v7v6

v4

v5

v4

v5

数据结构

0v1 ,

1 v1

v2

v3

2 v2 3 V3 4 V45 v5 6 v6 7 v7 8 v8

v1v1

v4v6

v5v7

v2 ,

v3

v1

v4 ,

v5

v2v2

v8v2

v8

v8 ,

v3v3

v7v6

v4

v5

v4

v5

数据结构

0v1 ,

1 v1

v2

v3

2 v2 3 V3 4 V45 v5 6 v6 7 v7 8 v8

v1v1

v4v6

v5v7

v2 ,

v3

v1

v4 ,

v5

v2v2

v8v2

v8

v8 ,

v3v3

v7v6

v4

v5 ,

v4

v5

数据结构

0v1 ,

1 v1

v2

v3

2 v2 3 V3 4 V45 v5 6 v6 7 v7 8 v8

v1v1

v4v6

v5v7

v2 ,

v3

v1

v4 ,

v5

v2v2

v8v2

v8

v8 ,

v3v3

v7v6

v4

v5 ,

v2

v8

v4

v5

数据结构

0v1 ,

1 v1

v2

v3

2 v2 3 V3 4 V45 v5 6 v6 7 v7 8 v8

v1v1

v4v6

v5v7

v2 ,

v3

v1

v4 ,

v5

v2v2

v8v2

v8

v8 ,

v3v3

v7v6

v4

v5 ,

v2

v8

v4

v5

本文来源：https://www.bwwdw.com/article/skp4.html