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

▶
为以下图形构造一棵最小生成树。
(包含图 (a)、(b)、(c))
# **(a) 图的邻接表**
节点:0, 1, 2, 3, 4, 5
```
0: (1,4), (2,5), (3,6), (4,5), (5,4)
1: (0,4), (2,4)
2: (1,4), (0,5), (3,8)
3: (2,8), (0,6), (4,8)
4: (3,8), (0,5), (5,4)
5: (4,4), (0,4)
```
---
# **(b) 图的邻接表**
城市节点:SF, LA, CHI, KC, BOS, NY, PHI, DC, ATL
根据图中边和权重整理如下:
```
SF: (LA,50), (CHI,100)
LA: (SF,50), (CHI,120), (KC,90)
CHI: (SF,100), (LA,120), (KC,40), (PHI,80), (NY,90), (BOS,90)
KC: (LA,90), (CHI,40), (PHI,70), (ATL,80)
BOS: (CHI,90), (NY,40)
NY: (BOS,40), (CHI,90), (PHI,30), (DC,30)
PHI: (CHI,80), (KC,70), (NY,30), (DC,35)
DC: (NY,30), (PHI,35), (ATL,60)
ATL: (KC,80), (DC,60)
```
---
# **(c) 图的邻接表**
节点:1,3,4,5,6,7,8
```
1: (2,6), (4,10), (8,2)
2: (1,6), (3,4), (7,4)
3: (2,4), (4,6), (6,2), (7,3)
4: (1,10), (3,6), (5,2)
5: (4,2), (6,6), (8,11)
6: (3,2), (5,6), (7,4)
7: (2,4), (3,3), (6,4), (8,6)
8: (1,2), (7,6), (5,11)
```
要求:必须使用 Prim 算法,并展示加入顶点和边的顺序。