电子科技大学：《软件技术基础 Fundamental of Software Technology》课程教学资源（课件讲稿）第三章 数据结构 3.6.3 图的遍历

电子斜技大学 软件技术基础 3.6.3图的遍历 主讲教师：刘民岷 航空航天学院 软件技术基础课程组

软件技术基础 主讲教师：刘民岷 航空航天学院 软件技术基础课程组

3、图的操作一一遍历 图的遍历(Traversing Graph.) 从图中指定顶点出发访问图中每一个顶点，且使每个顶点只被访 问一次，该过程为图的遍历。 ·图的遍历要比树结构复杂的多。出发点不同，任一顶点的邻接点 就不相同，路径也就不同。 ·因为图中元素是“多对多”的关系，为避免发生重复，设立一个 辅助数组visited,每访问一个顶点，便将其状态visited时置为 “真”。 常用的图的遍历方法有两种： - 深度优先遍历法 一广度优先遍历法 电子科技大学刘民岷 图 2

电子科技大学 刘民岷 图 2 ▪ 图的遍历（Traversing Graph） 从图中指定顶点出发访问图中每一个顶点，且使每个顶点只被访 问一次，该过程为图的遍历。 ▪ 图的遍历要比树结构复杂的多。出发点不同，任一顶点的邻接点 就不相同，路径也就不同。 ▪ 因为图中元素是“多对多”的关系，为避免发生重复，设立一个 辅助数组visited[]，每访问一个顶点，便将其状态visited[i]置为 “真” 。 ▪ 常用的图的遍历方法有两种： – 深度优先遍历法 – 广度优先遍历法

3、图的操作一一遍历（续） 3.1深度优先遍历 深度优先遍历法类似于树的先根遍历法。 算法思想： step1从图中某个顶点V0出发，并访问此顶点； step2从V0出发，访问与V0邻接的顶点V1后，再从V1出发，访问 与V1邻接且未被访问过的顶点V2。重复上述过程，直到不存在未 访问过的邻接点为止。 step3如果是连通图，从任一顶点V0出发，就可以遍历所有相邻 接的顶点；如果是非连通图，则再选择一个未被访问过的顶点作 为出发点，重复step1、step2,直到全部被访问过的邻接点都被 访问为止。 电子科技大学刘民岷 图 3

电子科技大学 刘民岷 图 3 3.1 深度优先遍历 • 深度优先遍历法类似于树的先根遍历法。 • 算法思想： –step1 从图中某个顶点V0出发，并访问此顶点； –step2 从V0出发，访问与V0邻接的顶点V1后，再从V1出发，访问 与V1邻接且未被访问过的顶点V2。重复上述过程，直到不存在未 访问过的邻接点为止。 –step3 如果是连通图，从任一顶点V0出发，就可以遍历所有相邻 接的顶点；如果是非连通图，则再选择一个未被访问过的顶点作 为出发点，重复step1、step2，直到全部被访问过的邻接点都被 访问为止

3、图的操作一一遍历（续） 3.1深度优先遍历 ·深度优先遍历举例 遍历过程 访问顶点 所过边 •起始顶点V1 V1 V1的第1个邻接点V3 V3 (V1,V3) V3的第1个邻接点V1已访问，取下 一个邻接点V5 V5 (V3,V5) V5的第1个邻接点V3已访问，取下 一个邻接点V2 V2 (V5,V2) V2的两个邻接点均被访问， 回退到V5,V5的邻接点均被访问， 回退到V3,V3的邻接点均被访问， G6 回退到V1,V1的另一个邻接点V4 未被访问 V4 (V1,V4) V4的第一个邻接点V1已被访问， 另一个邻接点V6未被访问 V6 (V4,V6) V6的邻接点被访问，回退到V4 V4的邻接点均被访问 回退到V1,返回到出发点，遍历结束。 电子科技大学刘民岷 图 4

电子科技大学 刘民岷 图 4 3.1 深度优先遍历 • 深度优先遍历举例 遍历过程 访问顶点 所过边 •起始顶点V1 V1 •V1的第1个邻接点V3 V3 （V1，V3） •V3的第1个邻接点V1已访问，取下 一个邻接点V5 V5 （V3，V5） •V5的第1个邻接点V3已访问，取下 一个邻接点V2 V2 （V5，V2） •V2的两个邻接点均被访问， 回退到V5，V5的邻接点均被访问， 回退到V3，V3的邻接点均被访问 ， 回退到V1，V1的另一个邻接点V4 未被访问 V4 （V1，V4） •V4的第一个邻接点V1已被访问， 另一个邻接点V6未被访问 V6 （V4，V6） •V6的邻接点被访问，回退到V4 •V4的邻接点均被访问 •回退到V1，返回到出发点，遍历结束。 V1 V3 V5 V4 V6 G6 V2

3、图的操作一一遍历（续） 3.2广度优先遍历 广度优先遍历法类似于树的按层次遍历的过程。即先访问 第1个顶点所有邻接点后，再访问下一个顶点所有未被访 问的邻接点。 算法思想： stepl从图中某个顶点VO出发，并访问此顶点； step2从V0出发，访问V0的各个未曾访问的邻接点W1, W2,.,Wk;然后，依次从W1W2,,Wk出发访问各自未被访问的邻 接点。 step3重复step2,直到全部顶点都被访问为止。 电子科技大学刘民岷 图 5

电子科技大学 刘民岷 图 5 3.2 广度优先遍历 • 广度优先遍历法类似于树的按层次遍历的过程。即先访问 第1个顶点所有邻接点后，再访问下一个顶点所有未被访 问的邻接点。 • 算法思想： – step1 从图中某个顶点V0出发，并访问此顶点； – step2 从V0出发，访问V0的各个未曾访问的邻接点W1， W2，…,Wk;然后,依次从W1,W2,…,Wk出发访问各自未被访问的邻 接点。 – step3 重复step2，直到全部顶点都被访问为止

3、图的操作一一遍历（续） 3.2广度优先遍历 ·广度优先遍历法举例 遍历过程 访问顶点 所过边 起始顶点V1 V1 访问V1的未被访问过 的所有邻接点 V3,V2,V4 (V1,V3) (V1,V2) V6 (V1,V4) G6 •访问V3的未被访问过 的所有的邻接点 V5 (V3,V5) •访问V2的未被访问过 的所有的邻接点 无 •访问V4的未被访问过 的所有的邻接点 V6 V4,V6) 所有顶点已被访问，结束。 电子科技大学刘民岷 图 6

电子科技大学 刘民岷 图 6 3.2 广度优先遍历 • 广度优先遍历法举例 遍历过程 访问顶点 所过边 •起始顶点V1 V1 •访问V1的未被访问过 的所有邻接点 V3,V2,V4 （V1，V3） (V1,V2) (V1,V4) •访问V3的未被访问过 的所有的邻接点 V5 （V3，V5） •访问V2的未被访问过 的所有的邻接点 无 •访问V4的未被访问过 的所有的邻接点 V6 (V4,V6) •所有顶点已被访问,结束。 V1 V3 V5 V4 V6 G6 V2