华中科技大学：《数据结构》课程教学资源（PPT课件讲稿）第七章 图 Graph 7.3 图的遍历 7.4 图的连通性问题

数特的 华中科技大学 计犷机学院(9 90008∞879

2001 -- 12 -- 27/29 华中科技大学 数据结构计算机学院(9)

7.3图的遍历一从图G的某定点vi出发,访问G的每个 顶点一次且一次的过程。 7.3.1图的深度优先搜索 DFS---Depth first Search 假定从A出发遍历图G: A ●A,E,G,F,H,B,D,C ●A,B,D,C,E,G,H,F ●A,B,F,G,H,E,C,D? ●A,E,F,H,G,B,C,D? ●A,F,G,H,E,B,D,C 图G 假定从G出发遍历图G: ●G,F,A,B,D,C,E,H ●G,H,F,A,E,B,D,C ●G,E,A,H,F,B,C,D?

7.3 图的遍历---- 从图G的某定点vi出发，访问G的每个 顶点一次且一次的过程。 7.3.1 图的深度优先搜索 DFS---Depth First Search F D B C A G H E 假定从 A 出发遍历图G： ● A,E,G,F,H,B,D,C ● A,B,D,C,E,G,H,F ● A,B,F,G,H,E,C,D ？ ● A,E,F,H,G,B,C,D ？ ● A,F,G,H,E,B,D,C 假定从G出发遍历图G： ● G,F,A,B,D,C,E,H ● G,H,F,A,E,B,D,C ● G,E,A,H,F,B,C,D ？ 图G

7.3.1图的广(宽)度优先搜索 BFS---Breadth first Search 假定从A出发遍历图G: ●A,E,F,B,G,H,I,D,C ●A,B,F,E,D,C,I,H,G ●A,F,E,G,H,I,B,D,C? ●A,F,B,E,G,H,I,C,D? ●A,E,B,F,I,H,G,D,C? 假定从G出发遍历G 图G ●G,F,E,H,A,I,B,C,D ●G,H,F,E,I,A,B3,C,D ●G,E,F,H,I,A,B,C,D?

7.3.1 图的广(宽)度优先搜索 BFS---Breadth First Search F D B C A G H E 假定从 A 出发遍历图G： ● A,E,F,B,G,H,I,D,C ● A,B,F,E,D,C,I,H,G ●A,F,E,G,H,I,B,D,C ？ ●A,F,B,E,G,H,I,C,D ？ ●A,E,B,F,I,H,G,D,C ？ 假定从 G 出发遍历G： ● G,F,E,H,A,I,B,C,D ● G,H,F,E,I,A,B,C,D ●G,E,F,H,I,A,B,C,D ？ I 图G

7.4图的连通性问题 7.4.1DFS生成树 假定从A出发DFS遍历图G: B B B 图G B

7.4 图的连通性问题 7.4.1 DFS生成树 假定从A出发DFS遍历图G： F D B C A G H E I 图G A B A B A B A D C D F D B C A F D B C A I F D B C A I G

7.4图的连通性问题 7.4.1DFS生成树 B B 图G ① DFS生成树T1 S生成树T2

7.4 图的连通性问题 7.4.1 DFS生成树 DFS生成树T1 F D B C A G H E I 图G F D B C A I G H F D B C A I G H E F D B C A G I E H DFS生成树T2 E C B D A I G F H

7.4.2BFS生成树 假定从A出发BFS遍历图G: AHB 图G →(A(B

7.4.2 BFS生成树 F D B C A G H E I 图G 假定从A出发BFS遍历图G： A A B A B F A B E F A B E F C A B E F C D A B E F C D I

7.4.2BFS生成树 假定从A出发BFS遍历图G: A(①c=( 图G ⑥④①⑦ ④①①C BFS生成树T1 BFS生成树T2

7.4.2 BFS生成树 F D B C A G H E I 图G 假定从A出发BFS遍历图G： A B E F C D I G H A B E F C D I H A E F B G H I D C A E F B G H I D C BFS生成树T1 BFS生成树T2

7.4.3DFS生成森林 从A出发,得树T1: ①① 9① D(F 图G TI 从G出发,得树T2: 从I出发,得树T3: ①① B T1 T2 T172

7.4.3 DFS生成森林 C K I J A D E B F G H 从A出发，得树T1： T2 C A D B E F 图G T3 T1 从G出发,得树T2： C A D B E F T1 G H T2 C A D B E F T1 G H K I J 从I出发,得树T3：

7.4.4BFS生成森林 从A出发,得树T1 9① ①画① 图G T1 从G出发,得树T2: 从I出发,得树T3: A B 画① ①① T1 T2

7.4.4 BFS生成森林 C K I J A D E B F G H 从A出发，得树T1： T2 图G T3 T1 从G出发,得树T2： A T1 G H T1 T2 G H K I J 从I出发,得树T3： C D E B F A C D E B F A C D E B F

7.4.5网的最小生成树: 在网G的各生成树中,其中各边的权之和最小的生成树称 为G的最小生成树 2 2 4 4 4 3 4 G 生成树1(13) 生成树2(12) 4 4 4 生成树3(10) 生成树4(11) 生成树5(10)

7.4.5 网的最小生成树: 在网G的各生成树中，其中各边的权之和最小的生成树称 为G的最小生成树 A C B D E 网G 1 2 4 3 4 A C B D E 生成树1（13） 2 4 3 4 A C B D E 生成树2（12） 1 4 3 4 A C B D E 生成树5（10） 1 2 4 3 A C B D E 生成树4（11） 1 2 4 4 D 生成树3（10） A C B E 1 2 3 4