<svg xmlns="http://www.w3.org/2000/svg" style="display: none;"> <path stroke-linecap="round" d="M5,0 0,2.5 5,5z" id="raphael-marker-block" style="-webkit-tap-highlight-color: rgba(0, 0, 0, 0);"></path> </svg> <p></p> 讯享网
- 什么是连通图？，首先理解什么是图？（这里面的学问其实有点大，所以我说咱们就是简单介绍下哈，本篇文章还是对有基础的朋友较友好，因为对于有基础的朋友，我可能是在废话哈哈哈）简单来说，平面内许多点通过一些路径相互连接（不一定要全部连接），就构成了一个图，而根据这些点之间的路径是否有方向，又分为了无向图和有向图。如下图，分别是一种无向图和有向图。
那么？什么是连通图呢？简单来说（只能简单来说了，说多了可以另起一篇文章。。。），就是图中的点通过图中的某些路径（带方向的就必须按照方向来）可以抵达任意一个点。最为简单的模型就是一个地区的许多村落之间的通信，如果每个村庄之间都可以达成通信，就是连通的。
- 最小生成树是什么呢？ 连通图中，每条路径都存在一个权值（理解为距离/成本也行吧，但其实不是这么理解的）。从该连通图出发，寻找一个路径数最少，但每个点之间都可达，就是一个生成树了（专业术语是连通无环子图）。生成树不止一个，而所以生成树中权值之和最小的生成树称为最小生成树。
- 算法开始，起始顶点可随机找或指定一个。将起始顶点先放入已选顶点集合中。
- 在未放入已选顶点集合中查找一条到已选顶点集合中所有点最短（或者是权值最小，这里看自己理解了）的路径（说是一条线或许更合适吧）。刚开始的话，我们已选顶点集合只有一个点！而之后我们会将未加入的顶点一个一个加入已选顶点集合，所以这里的条件必须是已选顶点集合中所有点。显然，在我们找到的这条最短（权值最小）路径的两端的顶点，一个肯定属于还未加入最小生成树中的顶点，另一个肯定属于已加入最小生成树的顶点。将还未加入已选顶点集合的那个点，加入已选顶点集合，本轮任务完成。如果需要路径的，可以将路径记录保存下来。
- 重复第二步，直到所有顶点已加入已选顶点集合，那么，我们的最小生成树就完成了。如果需要计算最小生成树的权值之和，在每一次找到最短路径的时候求一次和即可，需要具体路径的进行标记即可。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/137777.html