清华大学：《数据结构》课程电子教案（PPT课件讲稿）第六章 图

今深度优先遍历算法 递归算法 Ch6 1. txt 开始 开始 访问V0,置标志 标志数组初始化 求V0邻接点 有邻接点 V访问过 结束 DFS W访问过 ViVi+ W→VO求下一邻接点 Vi=Vexnums DFS 「结束 Ch6 1

❖深度优先遍历算法 ⚫递归算法 开始 访问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

例 深度遍历:VI=V3→V7→V6→V2→V5→V8→V4 vexdata firstarc ad]vex next 234567 12345678 35788765 24622334 1 入

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

例 深度遍历:VI=V3→V7→V6→V2→V4→V8→V5 vexdata firstarc ad]vex next 2 234567 12345678 347887 2

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出发,访问此顶点后,依次 访问∨0的各个未曾访问过的邻接点:然后分别从这些 邻接点出发,广度优先遍历图。直至图中所有已被访 问的顶点的邻接点都被访问到:若此时图中尚有顶点 未被访问,则另选图中一个未被访问的顶点作起点, 重复上述过程。直至图中所有顶点都被访问为止 广度遍历: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

例 广度遍历:V1→V2→V3→V4→V5→V6→V7→V8 例 V4)(8 广度遍历: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