<p id="main-toc"><strong>目录</strong></p> 讯享网
最小生成树的概念
经典题目
prim算法简介
prim算法解析 （详细图解）
代码实现
代码实战
在一给定的无向图G = (V, E) 中，(u, v) 代表连接顶点 u 与顶点 v 的边，而 w(u, v) 代表此的边权重，若存在 T 为 E 的子集（即）且为无循环图，使得的 w(T) 最小，则此 T 为 G 的最小生成树。最小生成树其实是最小权重生成树的简称。（简而言之就是把一个图变成一棵树，并且树中的边权和最小）
（这道题的数据过大，为了简化问题，我们假定数据范围可以用一个二维数组存下）
prim算法基于贪心，我们每次总是选出一个离生成树距离最小的点去加入生成树，最后实现最小生成树（不做证明，理解思想即可）
（随机构建一个无向图）
- 现在我们构建两个集合S（红色的点），V（蓝色的点），S集合中存放的是已近加入最小生成树的点，V集合中存放的是还没有加入最小生成树的点。显然刚开始时所有的点都在V集合中。
- 然后们先将任意一个点加入集合S中（默认为点1），并且初始化所有点（除了点1）到集合S的距离是无穷大。
- 用一个变量res存放最小生成树所有边权值的和。我们每次都选择离S集合最近的点加入S集合中，并且用新加入的点去更新dist数组，因为只有一个新的点加入到集合S中，到集合S的距离才有可能更新（贪心，每次都选最小的）。
- 更新就是看一下能否通过新加入的点使到达集合的距离变小（看下面dist数组的变化）。
- 我们开始在加入点1后开始第一次更新。
- 现在集合S={1}，集合V={2，3，4，5，6，7}，根据贪心策略，我们选择离集合S最近的点加入 ，即点2，并把这一条边的权值加到res中。
- 集合更新为S={1，2}，V={3，4，5，6，7}，并用点2去更新dist数组，我们发现点3和点7都可以都可以通过边2-3，2-7缩短到集合S得距离。
- 重复上面的步骤，直到将全部的点加入到最小生成树中。
- 3并不能更新任何点
- 这样一颗最小生成树就构建完成了，权值和是57。
讯享网
讯享网
纸上得来终觉浅，绝知此事要躬行，也许看完了上面的解析，你已经最prim算法有了一个大致的了解，学习算法，大致的了解是远远不够的，代码的实践永远是最重要的，学习完一个算法后一定要去自己亲手试试，每个人都有自己的代码风格，大家大可以在自己的风格之上写出自己的prim。
prim习题简介难度P3366 【模板】最小生成树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)模板题
★☆☆☆☆P1967 [NOIP2013 提高组] 货车运输 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)基本应用
★☆☆☆☆P1991 无线通讯网 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)基本应用
★☆☆☆☆
第一题是模板，后面两题主要是更好得帮助我们理解最小生成树——prim在实际和题目中得应用。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/183011.html