已知一个无向图的顶点集V和边集E分别为:V={A,B,C,D,E};E={(A,B)9,(A,D)3,(A,E)2,(B.C)1,(C,D)7,(D,E)4}。请回答以下问题: (1)画出该图的逻辑结构图示; (2)用普里姆算法求出该图从A顶点开始的最小生成树,并写出构造过程。
时间: 2024-02-27 19:53:44 浏览: 140
用Prim算法求无向图的最小生成树 (2).pdf
(1) 该图的逻辑结构图示如下:
```
9 1
A ------ B ------ C
| \ | |
3 | \2 |7 |
| \ | |
D ------ E ------
4
```
(2) 该图从顶点A开始的最小生成树构造过程如下:
1. 以A为起点,将A加入最小生成树中,标记A为已访问。
2. 将与A相邻的未访问顶点B、D、E的权值加入小根堆中。
3. 弹出小根堆中权值最小的边(A,E),将E加入最小生成树中,标记E为已访问。
4. 将与E相邻的未访问顶点D、F的权值加入小根堆中。
5. 弹出小根堆中权值最小的边(E,A),由于A已访问,直接舍弃。
6. 弹出小根堆中权值最小的边(E,D),将D加入最小生成树中,标记D为已访问。
7. 将与D相邻的未访问顶点C、E、G的权值加入小根堆中。
8. 弹出小根堆中权值最小的边(D,E),由于E已访问,直接舍弃。
9. 弹出小根堆中权值最小的边(D,C),将C加入最小生成树中,标记C为已访问。
10. 将与C相邻的未访问顶点B、D、F的权值加入小根堆中。
11. 弹出小根堆中权值最小的边(C,B),将B加入最小生成树中,标记B为已访问。
12. 将与B相邻的未访问顶点D、E的权值加入小根堆中。
13. 弹出小根堆中权值最小的边(B,C),由于C已访问,直接舍弃。
14. 弹出小根堆中权值最小的边(B,E),由于E已访问,直接舍弃。
15. 完成,最小生成树为:A -- E(2) -- D(4) -- C(1) -- B(9)。
阅读全文