大连理工大学：《数据结构》课程教学课件（PPT讲稿）第六章 图

冬深度优先遍历算法 ●递归算法 Ch6 1.txt 开始 开始 访问V0,置标志 标志数组初始化 求V0邻接点 Vi=1 有邻接点w N Vi访问过 结束 Y DFS Y W访问过 Vi=Vi+1 N w-V0 求下一邻接点 N Vj-=Vexnums Y DFS 结束 Ch6 1.c

❖深度优先遍历算法 ⚫递归算法 开始 访问V0,置标志 求V0邻接点 有邻接点w wV0 求下一邻接点 W访问过 结束 N Y N Y DFS 开始 标志数组初始化 Vi=1 Vi访问过 DFS Vi=Vi+1 Vi==Vexnums 结束 N N Y Y Ch6_1.c

例 (V2 V3 N⑧ 深度遍历：V1=V3→V7=→V6→V2→V5→V8→V4 vexdata firstarc adivex next 1 1 2 2 2 4 3 3 6 4 4 8 2 5 5 8 6 6 7 3 7 7 6 3 8 8 5 4

V1 V2 V4 V5 V3 V6 V7 V8 例 深度遍历：V1 1 2 3 4 1 3 4 2 vexdata firstarc 2 7 8 3 ^ ^ ^ adjvex next 5 5 6 5 4 1 ^ 1 2 8 2 ^ 6 7 8 6 7 8 7 3 6 3 5 4 ^ ^ ^ V3 V7 V6 V2 V5 V8 V4

例 V: 14 深度遍历：V1V3→V7→V6→V2→V4→V8=→V5 vexdata firstarc adivex next 2 2 4 3 2 6 4 8 5 5 8 6 7 7 8 8

V1 V2 V4 V5 V3 V6 V7 V8 例 1 2 3 4 1 3 4 2 vexdata firstarc 2 7 8 3 ^ ^ ^ adjvex next 5 5 6 4 ^ 8 2 ^ 6 7 8 6 7 8 7 ^ ^ ^ 深度遍历：V1V3 V7 V6 V2 V4 V8 V5

★广度优先遍历(BFS) 方法：从图的某一顶点V0出发，访问此顶点后，依次 访问V0的各个未曾访问过的邻接点；然后分别从这些 邻接点出发，广度优先遍历图，直至图中所有已被访 问的顶点的邻接点都被访问到：若此时图中尚有顶点 未被访问，则另选图中一个未被访问的顶点作起点， 重复上述过程，直至图中所有顶点都被访问为止 例 V2 V3 V: 广度遍历：V1→V2→V3→V4→V5→V6→V7→V8

广度优先遍历(BFS) ❖方法：从图的某一顶点V0出发，访问此顶点后，依次 访问V0的各个未曾访问过的邻接点；然后分别从这些 邻接点出发，广度优先遍历图，直至图中所有已被访 问的顶点的邻接点都被访问到；若此时图中尚有顶点 未被访问，则另选图中一个未被访问的顶点作起点， 重复上述过程，直至图中所有顶点都被访问为止 V1 V2 V4 V5 V3 V6 V7 V8 例 广度遍历：V1V2 V3  V4 V5 V6 V7 V8

例 (V3 Vs 广度遍历：V1=V2→V3→V4→V5=V6=V7=→V8 例 V3 V4 W⑧ Vi 广度遍历：V1三V2→V3→V4→V5→V6→V7→V8

V1 V2 V4 V5 V3 V6 V7 V8 例 例 V1 V2 V4 V5 V3 V7 V6 V8 广度遍历：V1V2 V3  V4 V5 V6 V7 V8 广度遍历：V1V2 V3  V4 V5 V6 V7 V8