kruskal算法在不连通图中求最小权生成林伪代码算法
时间: 2023-06-18 20:07:16 浏览: 62
Kruskal算法用于求解无向图的最小生成树问题,而最小生成树是一棵树,因此只适用于连通图。不过,我们可以把不连通图转化为生成森林,即多棵生成树的集合。下面是Kruskal算法在不连通图中求最小权生成森林的伪代码算法:
1.初始化:将每个顶点看作是一棵生成树,每个顶点的祖先是它自己。
2.将边按权值从小到大排序。
3.依次取出每条边,如果边的两个端点不在同一棵生成树中,则将它们所在的生成树合并成一棵树,边加入生成树的边集中。
4.重复步骤3,直到所有顶点都在同一棵生成树中。
下面是伪代码实现:
```
function Kruskal(G):
for each vertex v in G:
makeSet(v)
sort edges of G by weight
for each edge e in G:
if findSet(e.u) != findSet(e.v):
unionSet(e.u, e.v)
add e to the set of edges of the spanning forest
return the set of edges of the spanning forest
function makeSet(v):
v.parent = v
function findSet(v):
if v.parent == v:
return v
else:
return findSet(v.parent)
function unionSet(u, v):
uRoot = findSet(u)
vRoot = findSet(v)
uRoot.parent = vRoot
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![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)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![azw3](https://img-home.csdnimg.cn/images/20210720083646.png)