本文小编为大家详细介绍“Java如何实现Kruskal算法”，内容详细，步骤清晰，细节处理妥当，希望这篇“Java如何实现Kruskal算法”文章能帮助大家解决疑惑，下面跟着小编的思路慢慢深入，一起来学习新知识吧。构造最小生成树还有一种算法，即 Kruskal 算法：设图 G=（V，E）是无向连通带权图，V={1,2，…n};设最小生成树 T=(V，TE)，该树的初始状态只有 n 个节点而无边的非连通图T=(V,{}),Kruskal 算法将这n 个节点看成 n 个孤立的连通分支。它首先将所有边都按权值从小到大排序，然后值要在 T 中选的边数不到 n-1,就做这样贪心选择：在边集 E 中选择权值最小的边(i,j),如果将边(i,j)加入集合 TE 中不产生回路，则将边(i,j)加入边集 TE 中，即用边(i，j)将这两个分支合并成一个连通分支；否则继续选择下一条最短边。把边(i,j)从集合 E 中删去，继续上面的贪心选择，直到 T 中的所有节点都在同一个连通分支上为止。此时，选取的 n-1 条边恰好构成图 G 的一免费云主机域名棵最小生成树 T。Kruskal 算法用一种非常聪明的方法，就是运用集合避圈；如果所选择加入边的起点和终点都在 T 集合中，就可以断定会形成回路，变的两个节点不能属于同一个集合。算法步骤1 初始化。将所有边都按权值从小到大排序，将每个节点集合号都初始化为自身编号。2 按排序后的顺序选择权值最小的边（u,v）。3 如果节点 u 和 v 属于两个不同的连通分支，则将边(u,v)加入边集 TE 中，并将两个连通分支合并。4 如果选取的边数小于 n-1,则转向步骤2，否则算法结束。绿色为输入，白色为输出。读到这里，这篇“Java如何实现Kruskal算法”文章已经介绍完毕，想要掌握这篇文章的知识点还需要大家自己动手实践使用过才能领会，如果想了解更多相关内容的文章，欢迎关注百云主机行业资讯频道。
今天小编给大家分享一下ThinkPHP5如何查询昨天的数据的相关知识点，内容详细，逻辑清晰，相信大部分人都还太了解这方面的知识，所以分享这篇文章给大家参考一下，希望大家阅读完这篇文章后有所收获，下面我们一起来了解一下吧。 ThinkPHP5查询昨天数据的方法：…
免责声明：本站发布的图片视频文字，以转载和分享为主，文章观点不代表本站立场，本站不承担相关法律责任；如果涉及侵权请联系邮箱：360163164@qq.com举报，并提供相关证据，经查实将立刻删除涉嫌侵权内容。
微信扫一扫 
