
▶
# **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)
```