prim算法csdn（prim算法适用于什么图）



        连通图的生成树就是包含图中全部顶点的一个极小连通子图，如果图中顶点个数为n则生成树含有n-1条边，我们之前也了解到求广度优先生成树和深度优先生成树的方法。那么到底什么是最小生成树呢？其实最小生成树MST又叫最小代价树，就是边权值之和最小的生成树。

这里我们学习两种构建最小生成树的方法——prim算法、kruskal算法

prim算法就是从一个顶点开始，每次将代价最小的新顶点纳入生成树，就得到了最小生成树。这是一种贪心的思想，很好理解。用这种方法得到的最小生成树可能不同，但是权值之和一定是相同的。

kruskal算法就是每次都从所有的边中选择一条权值最小的边使这条边两头连通（如果原本已经连通就不选，否则会出现回路），就这样直至所有节点都连通。

对比以上两种算法Prim算法从顶点开始时间复杂度为O(|V^2|),Kruskal算法从边开始时间复杂度为O(|E|log|E|)，因此prim算法适合边稠密图，kruskal算法适合边稀疏图。

        要想实现prim算法可以借助两个数组，一个数组标记各节点是否加入最小生成树，一个节点记录各个节点加入树的最低代价lowcost[]（也就是该节点与生成树相连的边中最小的，如果边不存在则记为无穷），我们只需循环遍历没有加入树的结点，将离生成树距离最小的结点加入，并且更新lowcost[]数组，更新lowcost数组时，只需考虑剩下的结点与新加入的点的距离是否小于原本记录的记录，如果小于则更新，反之则不更新。这样直至所有结点加入生成树即可。

        而要想实现kruskal算法，需要先将所有边按照权值大小排序，这里结点的连接我们可以借助并查集进行操作。我们可以先把每个节点看作分属不同的集合，当我们从小到大遍历所有边时，当边两端的两个结点属于不同的集合时(通过查操作)，就可以把两个节点属于的集合并起来，并且把这条边选中。由于判断两个结点是否属于同一个集合的时间复杂度为O(log|E|)，所以其时间复杂度为O(|E|log|E|)。

版权声明：

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

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