已知一个无向图所示,要求分别用Prim和Kruskal算法生成最小树(假设以V1为起点,只画最小 生成树,不需要画过程)
时间: 2024-05-12 19:15:05 浏览: 171
用Prim算法求无向图的最小生成树.doc
抱歉,由于无法插入图片,我将无法为您提供图示,但我可以描述这两种算法的操作步骤。
假设我们有以下无向图:
```
6
(2)------(3)
/ \ / \
8 / \ 7 / \ 9
/ \ / \
(1)-------(4)------(5)
\ / \ /
11\ 2/ \4 / 14
\ / \ /
(6)------(7)
10
```
其中,数字表示边的权重,括号中的数字表示节点编号。
使用Prim算法生成最小生成树的步骤如下:
1. 选择一个起点,将其加入最小生成树的集合中。
2. 找到与当前最小生成树集合相邻的、权重最小的边,并将其加入最小生成树的集合中。
3. 重复步骤2,直到最小生成树中的节点数量等于图中节点数量。
以V1为起点,Prim算法生成的最小生成树为:
```
6
(2)------(3)
/
7/
/
(4)------(5)
| /
2| / 9
| /
(6)
```
使用Kruskal算法生成最小生成树的步骤如下:
1. 将所有边按照权重从小到大排序。
2. 从权重最小的边开始,依次加入最小生成树的集合中,如果加入该边会形成环,则不加入。
3. 重复步骤2,直到最小生成树中的节点数量等于图中节点数量。
Kruskal算法生成的最小生成树为:
```
6
(2)------(3)
/
7/
/
(4)------(5)
|
2|
|
(6)
```
阅读全文