最小生成树

发布时间:2018-11-24 08:52:31 作者:ex_jason 阅读量:497

最小生成树Kruskal算法

Kruskal算法的思想比Prim好理解一些,也比prim更好用。先把边按照权值进行排序,用贪心的思想优先选取权值较小的边,并依次连接,若出现环则跳过此边(用并查集来判断是否存在环)继续搜,直到已经使用的边的数量比总点数少一即可。

证明:刚刚有提到:如果某个连通图属于最小生成树,那么所有从外部连接到该连通图的边中的一条最短的边必然属于最小生成树。所以不难发现,当最小生成树被拆分成彼此独立的若干个连通分量的时候,所有能够连接任意两个连通分量的边中的一条最短边必然属于最小生成树。

具体算法流程图解如下:


代码

我要评论 登录后才能发布评论

网友评论


alanyhq

评论时间:2018-10-27 15:08:51

我搬的第一篇文章啦啦啦啦

推荐阅读

 2019-02-09 14:45:09   ex_jason

古人的劝谏艺术

 2019-01-25 10:53:14   ex_jason

【服务器】使用 KMS 激活 M...

 2018-12-14 20:44:05   ex_jason

我是我吗

 2018-11-24 08:54:16   ex_jason

题解洛谷 P1063 【能量项链...

 2018-11-24 08:53:32   ex_jason

关于NOIP的注意事项?CCF官...

 2018-11-24 08:52:31   ex_jason

最小生成树
ex_jason的博客 "    我要留言
Catfish(鲶鱼) CMS V 4.8.57