举一个kruskal算法的例子
时间: 2023-12-18 15:21:49 浏览: 71
Kruskal算法的实现
5星 · 资源好评率100%
好的,这里给你一个Kruskal算法的例子。
假设有以下这张图,我们要用Kruskal算法求出最小生成树:
![Kruskal算法例子](https://img-blog.csdnimg.cn/20210730211254795.png)
步骤如下:
1. 把所有边按权值从小到大排序;
2. 从权值最小的边开始,依次加入图中;
3. 如果加入某条边会形成环路,则不加入该边;
4. 直到加入n-1条边为止,n为节点个数,此时所有边都在最小生成树中。
按照上述步骤,我们可以得到以下最小生成树:
![最小生成树](https://img-blog.csdnimg.cn/2021073021230793.png)
以上就是Kruskal算法的一个例子。
阅读全文