Question

请对下图的无向带权图：1写出它的邻接矩阵，并按普里姆算法求其最小生成树；

1写出它的邻接矩阵，并按普里姆算法求其最小生成树；
2写出它的邻接表，并按克鲁斯卡尔算法求其最小生成树。

Answer 1

1. 邻接矩阵
A B C D E F G H
A 0 4 3 - - - - -
B 4 0 5 5 9 - - -
C 3 5 0 5 - - - 5
D - 5 5 0 7 6 5 4
E - 9 - 7 0 3 - -
F - - - 6 3 0 2 -
G - - - 5 - 2 0 6
H - - 5 4 - - 6 0

2.邻接表
A| B C
B| A C D E
C| A B D H
D| B C E F G H
E| B D F
F| E D G
G| D F H
H| C D G

3.普里姆算法求其最小生成树
选择原点为A
1. A-C
2. A-B
|
C
3. A-B
|
C-D
4. A-B
|
C-D-H
5. A-B
|
C-D-H
|
G
7. A-B
|
C-D-H
|
G
|
F-E

总距离：26

4.克鲁斯卡尔算法求其最小生成树
1. E-F
2. E-F
A-C
3. E-F
A-C
D-H
4. E-F
D-H
B-A-C
5. B-A-C
G-D-H
E-F
6. B-A-C-H-D-G
E-F
7. B-A-C-H-D-G-F-E

总距离：26

希望能帮到你