2.【严题集77②】请对下图的无向带权图 (1)写出它的邻接矩阵,并按普里姆算法求其最小生成树; (2)写出它的邻接表,并按克鲁斯卡尔算法求其最小生成树。 解:设起点为a。可以直接由原始图画出最小生成树,而且最小生 成树只有一种(类)! 邻接矩阵为: 00000 043∞000 55 最小生成树→ 0∞6 703 63020 o∞5400 206 PRIM算法(横向变化) (b, c, d, e, f, g, h (a, c)(b,d,e,f,g, h) (a,c, b)(d,e,f,g, h) lowcost 00od ddd (a, c, b, d) (e, f,g, h) 0oo d do (a,c, b, d, h(e, f,g) lowcost d g00 (a,c, b, d, h,(fe) lowcost lol 0 (a, c, b, d, h,te) f) 0000000{a,cb,d,h,{ g, f, e 邻接表为: 355 6-gs1-|44 2. 【严题集 7.7②】请对下图的无向带权图： （1） 写出它的邻接矩阵，并按普里姆算法求其最小生成树； （2） 写出它的邻接表，并按克鲁斯卡尔算法求其最小生成树。 解：设起点为 a。可以直接由原始图画出最小生成树，而且最小生 成树只有一种（类）! 邻接矩阵为： PRIM 算法（横向变化）： V b c d e f g h U V-U Vex lowcost a 4 a 3 a ∞ a ∞ a ∞ a ∞ a ∞ {a} {b,c,d,e,f,g,h} Vex lowcost a 4 0 c 5 a ∞ a ∞ a ∞ c 5 {a,c} {b, d,e,f,g,h} Vex lowcost 0 0 c 5 b 9 a ∞ a ∞ c 5 {a,c,b} {d,e,f,g,h} Vex lowcost 0 0 0 d 7 d 6 d 5 d 4 {a,c,b,d } {e,f,g,h} Vex lowcost 0 0 0 d 7 d 6 d 5 0 {a,c,b,d ,h } {e,f,g } Vex lowcost 0 0 0 d 7 g 2 0 0 {a,c,b,d ,h , g} { f,e } Vex lowcost 0 0 0 f 3 0 0 0 {a,c,b,d ,h , g, f } {e } Vex lowcost 0 0 0 0 0 0 0 {a,c,b,d ,h , g, f, e } { } 邻接表为： a → b 4 → c 3 b → a 4 → c 5 → d 5 → e 9 ^ c → a 3 → b 5 → d 5 → h 5 ^ d → b 5 → c 5 → e 7 → f 6 → g 5 → h 4^ e → b 9 → d 7 → f 3 ^ f → d 6 → e 3 → g 2 ^                                               5 4 6 0 5 2 0 6 6 3 0 2 9 7 0 3 5 5 0 7 6 5 4 3 5 0 5 5 4 0 5 5 9 0 4 3 最小生成树→