登录
注册
关注
TOP

查看: 822|回复: 7
收起左侧

[树/链表/图] 找最小生成树的算法思路

[复制链接] |只看干货 |树/链表/图, 刷题

升级   40%


分享帖子到朋友圈
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   100% (2)
 
 
0% (0)    👎

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
假设一个图的边的权值都在1到n的整数范围内,如何设计一种O(n(V+E))的算法来找这个图的最小生成树呢?(ps: 之前发的贴题目有误,实在不好意思!!)
感谢!!!

上一篇:我的刷题摸索贴
下一篇:为什么自己如此的弱

升级   3.2%

阿钟 2020-2-5 08:00:15 | 显示全部楼层
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   98% (1922)
 
 
1% (31)    👎
619899442 发表于 2020-2-5 07:13
In Kruskal Algorithm, instead of sorting edges by weight, build a reverse index (weight -> [edges]), ...

我觉得这个跟bucket sort有点像 但是runtime能不能降到n(V+E)?因为感觉union find总有一个log
回复

使用道具 举报

升级   28%

syia 2020-2-5 05:51:45 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   93% (27)
 
 
6% (2)    👎
回复

使用道具 举报

升级   40%

 楼主| ttt111223xx 2020-2-5 06:24:39 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (2)
 
 
0% (0)    👎
syia 发表于 2020-2-5 05:51
kruscal: https://www.youtube.com/watch?v=fAuF0EuZVCk
primm: https://www.youtube.com/watch?v=oP2-8ys ...

谢谢啊!但题目要找的是O(n(V+E))的算法,以上这俩个时间复杂度都不符合哈,有没有其它符合O(n(V+E))时间复杂的算法呢
回复

使用道具 举报

升级   0.83%

619899442 2020-2-5 07:13:16 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (136)
 
 
1% (2)    👎
In Kruskal Algorithm, instead of sorting edges by weight, build a reverse index (weight -> [edges]), and iterate each edge in increasing weight order (from 1 to n).
回复

使用道具 举报

升级   0.83%

619899442 2020-2-5 08:36:39 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (136)
 
 
1% (2)    👎
阿钟 发表于 2020-2-5 08:00
我觉得这个跟bucket sort有点像 但是runtime能不能降到n(V+E)?因为感觉union find总有一个log

path compression + ranking 可以给出近似于Constant time:https://en.wikipedia.org/wiki/Di ... ure#Time_complexity
回复

使用道具 举报

升级   3.2%

阿钟 2020-2-5 08:55:04 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (1922)
 
 
1% (31)    👎
阿钟 发表于 2020-2-5 08:00
我觉得这个跟bucket sort有点像 但是runtime能不能降到n(V+E)?因为感觉union find总有一个log

哦 inverse ackermann永远 <5, good to know...
回复

使用道具 举报

升级   40%

 楼主| ttt111223xx 2020-2-5 13:22:04 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (2)
 
 
0% (0)    👎
619899442 发表于 2020-2-5 07:13
In Kruskal Algorithm, instead of sorting edges by weight, build a reverse index (weight -> [edges]), ...

有点没懂"build a reverse index (weight -> [edges])",可以再稍微解释一下吗,谢谢啦
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■拉群请前往同学同事飞友|拉群结伴版块,其他版块拉群,帖子会被自动删除
■论坛不能删帖,为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://tools.1point3acres.com/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

论坛导航
快速回复 返回顶部 返回列表