采用Kruskal与Prim算法求出该图的最小生成树。要求给出步骤,画出过程图。
时间: 2023-12-10 15:42:22 浏览: 49
首先给出图的邻接矩阵表示:
```
0 6 1 ∞ ∞ ∞
6 0 5 3 ∞ ∞
1 5 0 5 6 ∞
∞ 3 5 0 4 2
∞ ∞ 6 4 0 6
∞ ∞ ∞ 2 6 0
```
其中 ∞ 表示两点之间没有边相连。
### Kruskal算法
Kruskal算法是按照边权值递增的顺序,每次加入一条边,如果这条边所连的两个点不在同一个连通块中,则将它们合并成一个连通块,直到所有点都在同一个连通块中为止。
1. 将所有边按照权值从小到大排序。
```
(1, 3):1 (3, 6):2 (2, 4):3 (4, 5):3 (2, 3):5 (3, 4):5 (4, 6):6 (1, 2):6 (3, 5):6 (5, 6):6
```
2. 从权值最小的边开始,加入到最小生成树中。
```
(1, 3):1
```
3. 加入下一条权值最小的边。
```
(1, 3):1 (3, 6):2
```
4. 加入下一条权值最小的边。
```
(1, 3):1 (3, 6):2 (1, 2):6
```
5. 加入下一条权值最小的边。
```
(1, 3):1 (3, 6):2 (1, 2):6 (4, 5):3
```
6. 加入下一条权值最小的边。
```
(1, 3):1 (3, 6):2 (1, 2):6 (4, 5):3 (2, 4):3
```
7. 加入下一条权值最小的边。
```
(1, 3):1 (3, 6):2 (1, 2):6 (4, 5):3 (2, 4):3 (4, 6):6
```
8. 加入下一条权值最小的边。
```
(1, 3):1 (3, 6):2 (1, 2):6 (4, 5):3 (2, 4):3 (4, 6):6 (3, 5):6
```
最终得到的最小生成树为:
```
(1, 3):1 (3, 6):2 (4, 5):3 (2, 4):3 (1, 2):6
```
### Prim算法
Prim算法是从一个点开始,每次找到与已有的点集距离最近的点加入到集合中,直到所有点都在集合中为止。
1. 选择一个起点(这里选择1号点)。
```
1
```
2. 将所有与1号点直接相连的边加入到集合中。
```
(1, 3):1 (1, 2):6
```
3. 从集合中找到距离最近的点(这里是3号点),将所有与它直接相连的边加入到集合中。
```
(1, 3):1 (3, 6):2 (1, 2):6 (3, 4):5
```
4. 从集合中找到距离最近的点(这里是6号点),将所有与它直接相连的边加入到集合中。
```
(1, 3):1 (3, 6):2 (1, 2):6 (3, 4):5 (4, 6):6 (3, 5):6
```
5. 从集合中找到距离最近的点(这里是4号点),将所有与它直接相连的边加入到集合中。
```
(1, 3):1 (3, 6):2 (1, 2):6 (3, 4):5 (4, 6):6 (3, 5):6 (2, 4):3
```
最终得到的最小生成树为:
```
(1, 3):1 (3, 6):2 (3, 4):5 (2, 4):3 (1, 2):6
```
相关推荐
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)