请举一个prim算法的例子
时间: 2023-08-14 15:31:23 浏览: 33
好的,我们来看一个简单的 Prim 算法的例子:
假设有如下无向带权图,其中节点用字母表示,边上的数字表示边的权值。
```
7
A-----B
/| |\
5 | | 9
\| |/
C-----D
6
```
我们从节点 A 开始,将其加入生成树中,然后分别考虑与节点 A 相邻的边,即 AB、AC、AD。其中,AB 的权值最小,因此将其加入生成树中。此时,生成树包含了节点 A 和节点 B,边权和为 7。
```
7
A-----B
\
5 \
\ 9
\
D
```
接下来,我们考虑与节点 A 和节点 B 相邻的边,即 AC、AD 和 BC。其中,AC 的权值最小,因此将其加入生成树中。此时,生成树包含了节点 A、B 和节点 C,边权和为 12。
```
7
A-----B
\ |
5 \ | 9
\ |
\|
C
```
现在,我们考虑与节点 A、B 和节点 C 相邻的边,即 AD、BC 和 CD。其中,BC 的权值最小,因此将其加入生成树中。此时,生成树包含了所有节点,边权和为 21。
```
7
A-----B
\ |
5 \ | 9
\ |
\|
C
\
\6
\
D
```
因此,最小生成树为:
```
7
A-----B
\
5 \
\ 9
\
D
```
边权和为 21。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.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)