图的遍历 n遍历方式 深度优先遍历DFs( Depth First Search) 从顶点v1出发,访问任一未被访问的邻接顶点v2 >再从顶点v2出发,访问任一未被访问的邻接顶点v3 再从顶点v3出发,…,如此进行下去,直到所有邻接 顶点都被访问过为止 退回一步到刚被访问的顶点,看是否有未被访问的邻 接顶点。 口若有,则继续访问 口否则,再退回一步 直到所有顶点都被访问 17
图的遍历 ◼ 遍历方式 深度优先遍历 DFS (Depth First Search) ➢ 从顶点v1出发，访问任一未被访问的邻接顶点v2 ; ➢ 再从顶点v2出发，访问任一未被访问的邻接顶点v3 ; ➢ 再从顶点v3出发，… ，如此进行下去，直到所有邻接 顶点都被访问过为止 ➢ 退回一步到刚被访问的顶点，看是否有未被访问的邻 接顶点。 若有，则继续访问 否则，再退回一步 ➢ 直到所有顶点都被访问 17
图的遍历 n遍历方式 深度优先遍历DFs( Depth First Search) 3前进→> AB—E回退 E D c)5(G4 c)5(G4 6F丝HD FH 8 深度优先搜索过程 深度优先生成树 18
图的遍历 ◼ 遍历方式 深度优先遍历 DFS (Depth First Search) 18 前进 回退 深度优先搜索过程 深度优先生成树 A B E D C G F H I 1 2 3 5 4 6 7 8 9 A B E D C G F H I 1 2 3 5 4 6 7 8 9
图的遍历 n遍历方式 口广度优先遍历BFs( Breadth First Search) 从起始顶点咄出发,依次访问v的未被访问的邻接顶点 1W2 顺序访问W1,W2,…,wn的所有未被访问的邻接顶点, 以此类推,直到所有顶点都被访问 19
图的遍历 ◼ 遍历方式 广度优先遍历 BFS (Breadth First Search) ➢ 从起始顶点v出发，依次访问v的未被访问的邻接顶点 w1 , w2 , … , wm ➢ 顺序访问w1 , w2 , … , wm的所有未被访问的邻接顶点, 以此类推，直到所有顶点都被访问 19
图的遍历 n遍历方式 口广度优先遍历BFs( Breadth First Search) B B E D)3c)!1G)7 4D)3c G5 AH H 8 广度优先搜索过程 广度优先生成树 20
图的遍历 ◼ 遍历方式 广度优先遍历 BFS (Breadth First Search) 广度优先搜索过程 广度优先生成树 20 A B E D C G F H I 1 2 5 3 7 6 4 8 9 A B E D C G F H I 1 2 5 3 5 6 4 8 9