济南大学信息科学与工程学院数据结构课件 第八章（3）.ppt

最小生成树Prim算法示意图 最小生成树Kruskal算法示意图 * * 第8章 图 8.1 （1） 不是强连通图，每个顶点单独构成各个强连通分量 （2）简单路径： A?B, A?D, A?B?C, A?B?E, A?D?B, A?D?E A?B?C?F, …… B?C, B?E, B?C?F, B?C?F?E C?F,C?F?E D?B, D?E, D?B?C, D?B?E, D?B?C?F,…… F?E 有向环： 无 （3）每个顶点的入度和出度 1 0 2 1 2 2 出度 1 3 1 1 2 0 入度 F E D C B A 顶点 图的邻接表 图的逆邻接表 （4）图的邻接矩阵 A B C D E F A B C D E F 0 1 2 3 4 5 1 ∧ 2 F ∧ 3 5 E ∧ 0 D ∧ 1 C ∧ 0 3 B ∧ A ∧ 4 F ∧ E ∧ 1 4 D ∧ 5 C ∧ 2 4 B ∧ 1 3 A 0 1 2 3 4 5 8.10（1）解：从顶点1出发的 深度优先有哪些信誉好的足球投注网站生成树 （2）解：从顶点2出发的 广度优先有哪些信誉好的足球投注网站生成树 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 原图 1 2 4 5 3 或 补充作业1： 从顶点1开始分别用Prim算法和Kruskal 算法构造下图的 最小生成树 ， 要求分步画写中间过程 1 2 4 5 6 3 16 5 10 6 21 11 14 33 18 19 1 2 4 5 6 3 1 2 4 5 6 3 16 5 1 2 4 5 6 3 16 5 6 11 16 16 5 6 1 2 4 5 6 3 1 2 4 5 6 3 16 5 6 11 18 1 2 4 5 6 3 16 5 6 11 18 21 19 33 14 10 1 2 4 5 6 3 1 2 4 5 6 3 1 2 4 5 6 3 5 1 2 4 5 6 3 16 5 6 11 11 5 6 1 2 4 5 6 3 1 2 4 5 6 3 16 5 6 11 18 5 6 补充作业2：应用Dijkstra 算法求 A 到其它各点的最短路径及长度 A B E C D F 45 10 30 35 3 20 15 15 50 10 20 新终点 路径长度 最短路径 F E D C B { } S 终点 50 10 ∞ 45 ∞ 10 (A,C) C {C} 50 25 45 ∞ 25 (A,C,D) D {C,D} 45 45 ∞ 45 (A,C,D,B) B 45 ∞ {B,C,D} 45 (A,E) E {B,C,D,E} ∞ ∞ 无 F 作业2 补充作业3：下图是一AOE网求出其关键路径。（画出关键路径或给出关键路径顶点序列） 关键路径长度=18 *