# **Section 3** ## **题目 2** 使用 Kruskal 算法为下面的图找到一棵最小生成树。 除了得到最小生成树外，还要给出算法过程中最终形成的根树。 在合并两棵树时，以编号较小的顶点作为新树的根。 Figure 16.3.13. Graph 2(a) ``` 1: (2,41), (5,21) 2: (1,41), (3,32), (5,42), (6,22) 3: (2,32), (4,29), (7,31) 4: (3,29), (7,23), (8,44) 5: (1,21), (2,42), (6,20) 6: (5,20), (2,22), (7,62) 7: (6,62), (3,31), (4,23), (8,45) 8: (7,45), (4,44) ``` Figure 16.3.14. Graph 2(b) ```text 1: (2, 10), (4, 7), (8, 10) 2: (1, 10), (3, 11), (5, 14), (7, 10) 3: (2, 11), (4, 12), (6, 16), (8, 8) 4: (1, 7), (3, 12), (5, 13), (7, 15) 5: (2, 14), (4, 13), (6, 13), (8, 9) 6: (1, 7), (3, 16), (5, 13), (7, 12) 7: (2, 10), (4, 15), (6, 12), (8, 11) ```