第8章图 (2)关节点为①,②,③,⑦,⑧ 3)至少加四条边(1,10),(3,4,(4,5)(5,6)。从③的子孙结点⑩到③的祖先结点①引一条边,从② 的子孙结点④到根①的另一分支③引一条边,并将⑦的子孙结点⑤、⑥与结点④连结起来,可使其变为 重连通图 7-11编写一个完整的程序,首先定义堆和并查集的结构类型和 相关操作,再定义 Kruskal求连通网络的最小生成树算法的实 现。并以右图为例,写出求解过程中堆、并查集和最小生成树7 的变化 【解答】 求解过程的第一步是对所有的边,按其权值大小建堆: 127 面应4应d 山27[31d 加(1,2),(1,3) 血3山[249 加(2,4) 加(3,4) 山27 127Bs7 B山区249]2lio 加(3,5) 加(3,6) [249[23o368]加(5.6 血 求解过程中并查集与堆的变化: s66 ④⑥ 368第 8 章 图 100 (2) 关节点为 ①,②,③,⑦,⑧ (3) 至少加四条边 (1, 10), (3, 4), (4, 5), (5, 6)。从③的子孙结点⑩到③的祖先结点①引一条边，从② 的子孙结点④到根①的另一分支③引一条边，并将⑦的子孙结点⑤、⑥与结点④连结起来，可使其变为 重连通图。 7-11 编写一个完整的程序，首先定义堆和并查集的结构类型和 相关操作，再定义 Kruskal 求连通网络的最小生成树算法的实 现。并以右图为例，写出求解过程中堆、并查集和最小生成树 的变化。 【解答】 求解过程的第一步是对所有的边，按其权值大小建堆： 求解过程中并查集与堆的变化： 1 3 11 ① ② ③ ④ ⑤ ⑥ 6 8 5 10 9 7 ⑩ ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ ⑨ ⑩ ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ ⑨ 1 2 7 1 3 11 2 3 10 1 2 7 2 4 9 2 3 10 1 3 11 3 4 5 1 2 7 2 3 10 2 4 9 加(1, 2), (1, 3), (2,3) 加(2, 4) 加(3, 4) 1 3 11 3 4 5 1 2 7 3 5 7 2 4 9 2 3 10 1 3 11 3 4 5 1 2 7 3 5 7 2 4 9 2 3 10 3 6 8 加(3, 5) 加(3, 6) 1 2 7 3 4 5 5 6 6 3 5 7 2 4 9 2 3 10 3 6 8 1 3 11 加(5, 6) ③ 5 6 6 1 2 7 3 5 7 ③ ④ ⑤ ⑥ 1 2 7 3 6 8 3 5 7