prim算法csdn（prim算法和kruskal算法的生成树一样吗）



上一篇文章，我们讲了图的创建和遍历，其中遍历的算法主要有BFS（广度优先算法）和DFS（深度优先算法）两种，并且DFS算法对很多问题都有很好的启示！而今天我们要说一个非常实用的算法——最小生成树的建立！这是图论中一个经典问题，可以使用Kruskal和Prim两种算法来进行实现！

1

什么是最小生成树

在给定一张无向图，如果在它的子图中，任意两个顶点都是互相连通，并且是一个树结构，那么这棵树叫做生成树。当连接顶点之间的图有权重时，权重之和最小的树结构为最小生成树！

在实际中，这种算法的应用非常广泛，比如我们需要在n个城市铺设电缆，则需要n-1条通信线路，那么我们如何铺设可以使得电缆最短呢？最小生成树就是为了解决这个问题而诞生的！

最小生成树 如上图所示，一幅两两相连的图中，找到一个子图，连接到所有的节点，并且连接边的权重最小（也就是说边的数量也是最小的，这也保证了其是树结构）.

2

Kruskal算法（克鲁斯卡算法）

Kruskal算法是一种贪心算法，我们将图中的每个edge按照权重大小进行排序，每次从边集中取出权重最小且两个顶点都不在同一个集合的边加入生成树中！注意：如果这两个顶点都在同一集合内，说明已经通过其他边相连，因此如果将这个边添加到生成树中，那么就会形成环！这样反复做，直到所有的节点都连接成功！

在这个算法中，最重要的一环就是判断两个节点在不在同一个集合内，很多人想，那你直接用一个set来保存不就好了？这是思路显然不行，因为假设A和其他三个节点相连，同属一个集合，而B和另外三个节点相连，同属一个集合，那么我们将A和B取并集时，是将这两组数据合并一起的，如果使用set，那么当数据量大时还需要遍历，复杂度就会很高，因此使用并查集就会效率快很多了！

3

Prim算法（普里姆算法）

Prim算法是另一种贪心算法，和Kruskal算法的贪心策略不同，Kruskal算法主要对边进行操作，而Prim算法则是对节点进行操作，每次遍历添加一个点，这时候我们就不需要使用并查集了。具体步骤为：

注意：对于单连通，从一个节点出发就可以直接找到完整的最小生成树，因此最外的for循环也可以为一个顺序结构，但多连通，就需要从不同的节点出发了！！！

那么对于这两种算法，我们应该用哪种呢？记得某个人说过这句话，算法没有优劣，每个算法都有它的使用场景，在对的场合使用对的算法，这才是算法工程师应该做的事情！

由于Kruskal算法是对边进行操作，先取出边，然后判断边的两个节点，这样的话，如果一个图结构非常的稠密，那么Kruskal算法就比较慢了，而Prim算法只是对节点进行遍历，并使用set进行标记，因此会相对于Kruskal算法，在稠密图方面好很多，因此Kruskal算法常用于稀疏图，而Prim算法常用于稠密图！

4

资源分享

以上完整代码文件（C++版）,文件名为：最小生成树（Kruskal算法和Prim算法）.cpp，请关注我的个人公众号 （算法工程师之路），回复"左神算法基础CPP"即可获得，并实时更新！希望大家多多支持哦~

公众号简介：分享算法工程师必备技能，谈谈那些有深度有意思的算法，主要范围：C++数据结构与算法/深度学习（CV），立志成为Offer收割机！坚持分享算法题目和解题思路（Day By Day)

完

▼

更多精彩推荐，请关注我们

▼

长按二维码关注算法工程师之路

算法工程师

我们一起努力，For World!

版权声明：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！

转载请注明出处，原文链接：https://www.xkablog.com/rfx/17332.html