1、深度优先搜索遍历(DFS)方法 ●深度优先搜索遍历类似于树的先根遍历,是树的先根 遍历的推广。 ●深度优先可以从图中某个顶点V出发,访问此顶点 然后依次从v的未被访问的邻接点出发,深度优先遍 历图,直至图中所有和V有路径的顶点都被访问到; 若此时图中尚有顶点未被访问,则另选图中一个未曾 被访问的顶点作起点,重复上述过程,直至图中所有 顶点都被访问为止 北京邮电大学自动化学院
北京邮电大学自动化学院 26 1、深度优先搜索遍历(DFS)方法 ⚫ 深度优先搜索遍历类似于树的先根遍历，是树的先根 遍历的推广。 ⚫ 深度优先可以从图中某个顶点V出发，访问此顶点， ⚫ 若此时图中尚有顶点未被访问，则另选图中一个未曾 被访问的顶点作起点，重复上述过程，直至图中所有 顶点都被访问为止。 ⚫ 然后依次从V的未被访问的邻接点出发，深度优先遍 历图，直至图中所有和V有路径的顶点都被访问到；
1、深度优先搜索遍历(DFS)方法 (1)假定从图中的某一顶点V出发进行遍历,首先访问 顶点V,再访问一个与Ⅴ相邻的顶点W,接着访问一个与 W相邻且未被访问的顶点。依次类推,直至某个被访问 的顶点的所有相邻顶点均被访问过为止。 ●(2)然后退回到尚有相邻顶点未被访问的顶点R,再从 顶点R的一个未被访问的相邻顶点出发,重复上述过 程,直到图中所有和V有路径相通的顶点都被访问过。 (3)若此时图中尚有顶点未被访问,则另选图中一个未 被访问的顶点作起点,重复上述过程,直至图中所有顶 点都被访问为止。 北京邮电大学自动化学院 27
北京邮电大学自动化学院 27 ⚫ （1）假定从图中的某一顶点V出发进行遍历，首先访问 顶点V，再访问一个与V相邻的顶点W，接着访问一个与 W相邻且未被访问的顶点。依次类推，直至某个被访问 的顶点的所有相邻顶点均被访问过为止。 ⚫ （2）然后退回到尚有相邻顶点未被访问的顶点R，再从 顶点R的一个未被访问的相邻顶点出发，重复上述过 程，直到图中所有和V有路径相通的顶点都被访问过。 ⚫ （3）若此时图中尚有顶点未被访问，则另选图中一个未 被访问的顶点作起点，重复上述过程，直至图中所有顶 点都被访问为止。 1、深度优先搜索遍历(DFS)方法
1、深度优先搜索遍历(DFS)方法 深度遍历:V1→V2→V4→V→Ⅴs→V3→V6→V7 vexdatafirstarc adivex next 2 例 234 4 12345678 35788765 6 2 3入 3∧ 4 北京邮电大学自动化学院
北京邮电大学自动化学院 28 深度遍历：V1 V2 V4 V8 V5 V3 V6 V7 1、深度优先搜索遍历(DFS)方法 V1 V2 V4 V5 V3 V6 V7 V8 例 1 2 3 4 1 3 4 2 vexdatafirstarc 2 7 8 3 ^ ^ ^ adjvexnext 5 5 6 5 4 1 ^ 1 2 8 2 ^ 6 7 8 6 7 8 7 3 6 3 5 4 ^ ^ ^
1、深度优先搜索遍历(DFS)方法 深度遍历:V1→V2→V4→V8→V5→V3→V6→V7 vexdatafirstarc adjvexnext 例 2 2345678 234 3=47887 6 5678 北京邮电大学自动化学院
北京邮电大学自动化学院 29 V1 V2 V4 V5 V3 V6 V7 V8 例 1 2 3 4 1 3 4 2 vexdatafirstarc 2 7 8 3 ^ ^ ^ adjvexnext 5 5 6 4 ^ 8 2 ^ 6 7 8 6 7 8 7 ^ ^ ^ 深度遍历：V1V2 V4 V8 V5 V3 V6 V7 1、深度优先搜索遍历(DFS)方法
2、广度优先搜索遍历(BFS) 方法:广度优先遍历类似于树的按层次遍历的过程。假设 从图中某顶点V出发,访问此顶点v后,依次访问v的各个 未曾访问过的邻接点; 然后分别从这些邻接点出发依次访问它们的邻接点,并使 “先被访问的顶点的邻接点”先于“后被访问的顶点的邻 接点”被访问,直至图中所有已被访问的顶点的邻接点都 被访问到; 若此时图中尚有顶点未被访问,则另选图中一个未被访 问的顶点作起点,重复上述过程,直至图中所有顶点都 被访问为止。 北京邮电大学自动化学院
北京邮电大学自动化学院 30 2、广度优先搜索遍历(BFS) ⚫ 方法：广度优先遍历类似于树的按层次遍历的过程。假设 从图中某顶点V出发，访问此顶点V后，依次访问V的各个 未曾访问过的邻接点； ⚫ 若此时图中尚有顶点未被访问，则另选图中一个未被访 问的顶点作起点，重复上述过程，直至图中所有顶点都 被访问为止。 ⚫ 然后分别从这些邻接点出发依次访问它们的邻接点，并使 “先被访问的顶点的邻接点”先于“后被访问的顶点的邻 接点”被访问，直至图中所有已被访问的顶点的邻接点都 被访问到；