腾讯云
开发者社区
文档
建议反馈
控制台
登录/注册
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
搜索
搜索
关闭
发布
精选内容/技术社群/优惠产品,
尽在小程序
立即前往
文章
问答
(9999+)
视频
沙龙
4
回答
如何在
线性
时间内计算
最小
瓶颈
生成
树
?
、
、
、
、
用Kruskal
算法
可以在最坏的情况下找到O(E log*V)中的
最小
瓶颈
生成
树
。这是因为每个
最小
生成
树
都是
最小
瓶颈
生成
树
。 但我被课程的面试问题困住了。在最坏的情况下,如何在
线性
时间内找到
最小
瓶颈
生成
树
。请注意,我们可以假设在最坏的情况下,我们可以在
线性
时间内计算n个键的中值。
浏览 23
提问于2014-04-05
得票数 5
回答已采纳
2
回答
最快
最小
生成
树
算法
、
我希望我的
最小
生成
树
算法
基准与最好的。有人知道在哪里可以找到这些
算法
的C++实现吗?我大摇大摆地搜索了一下,却什么也没找到。如果这些
算法
是最好的,那么肯定有一个C++实现吗?--迄今最快的
最小
生成
树
算法
是由David、Philip和Robert提出的,他发现了一种
线性
时间随机
算法
,它是Borůvka
算法
和反向删除
算法
的结合。函数α增长非常慢,因此
浏览 2
提问于2011-02-07
得票数 11
回答已采纳
1
回答
找到MST的临界边缘:用改进的Prim
算法
可能吗?
、
、
、
一个将运行Kruskal
算法
的修改版本:如果两个或多个相同权重的边缘连接相同的组件,从而形成一个循环,那么所有这些都是黄色边缘,即可以包含在MST中的边缘(或不包括)。上面的
算法
的问题是,它运行在O( {##*}*log\V# )中,这是Kruskal
算法
的运行时间(如果我错了,请纠正我)。我正在考虑是否也可以使用Prim
算法
的修改版本,因为如果使用Fibonacci堆,它具有更好的摊销复杂度的O( {##**$$}}E~*)的O(欧元E+V log log V_x )的更好的摊销复杂度。我的感觉是,这里不能使用Prim<
浏览 3
提问于2014-12-31
得票数 4
回答已采纳
1
回答
一种用于遍历图的
线性
时间
算法
、
、
、
我正在阅读一本
算法
教科书,以提高我的
算法
技能,但我在这个问题上完全被困住了,这让我很困扰。我认为底层的数据结构是一个图表,但我甚至不知道从哪里开始这个问题。有人能给点见解吗?提出了一个
线性
时间
算法
,该
算法
可以找到从s到t的路径,从而使最大高度
最小
化。道路可以双向通行。
浏览 3
提问于2013-10-01
得票数 1
1
回答
在
线性
时间内用红色或蓝色着色的图中的k条红边求
生成
树
、
、
给出了一个具有红边和蓝边的图G和一个常数K,设计了一个确定性的
线性
时间
算法
,它能找到G的
生成
树
(如果不存在这样的
生成
树
,则返回False )。找到
最小
生成
树
(使用标准
线性
时间
算法
)。因此,我们有一个具有
最小
权重的
生成
树
T,这意味着我们尽可能多地使用红色边,因为红色边只会减少权重。 如果T中有小于K的红边,则返回False。这是我们的问题,我们如何
浏览 1
提问于2014-02-11
得票数 4
2
回答
我在O(E/V)中找到了一个计算多个MSTs的
算法
。这个可以出版吗?
、
、
、
Kruskal和Prim已经使用优先级队列,但它们比下面列出的
线性
时间
算法
慢。 当权值为小整数时,可在
线性
最坏情况下求解。弗雷德曼和威拉德,“
最
浏览 2
提问于2013-12-20
得票数 0
回答已采纳
1
回答
设计了一种在
线性
时间内求图
最小
生成
树
的
算法
。
、
、
、
、
设计了一种在
线性
时间(O(n + m))内求G
最小
生成
树
的
算法
。 在我目前正在学习的
算法
图论课程中,我们讨论了Kruskal和Prim的MST
算法
。也许我可以在某种程度上修改这些,以获得
线性
时间。边的排序通常需要对数
线性
(O(mlog(M)时间;然而,由于所有的边权都是1,2或3,桶排序可以用来在边数(O(m))中对边进行时间
线性
排序。Kruskal的前两行,但是对于
算法</e
浏览 2
提问于2016-03-01
得票数 4
回答已采纳
2
回答
为什么当我们将G中的每个边的成本更改为c'= log17(C)时,G中的每个MST仍然是G‘中的MST (反之亦然)?
、
注:C‘为logc,基数为17用
线性
函数对每条边的代价进行变换,很容易证明结论是正确的。 我没有考虑具体的
算法
,比如贪婪的
算法
。我只考虑了变换后两棵
树
的权重之和之间的关系。如果G
生成
的一棵
树
有两个边a和b,由G
生成
的另一棵
树
有c和d,a+b<c+d,第一棵
树
是MST,但在
浏览 8
提问于2020-08-12
得票数 2
回答已采纳
2
回答
给定一个图,找到一个不是
最小
的
生成
树
、
、
、
如何找到图中不是
最小
的
生成
树
(如果可能)
浏览 4
提问于2016-05-02
得票数 0
1
回答
线性
时间中的MST
、
、
我正在准备
算法
的期末考试,我有一个问题,希望你们能帮我。 给定一个权重在1到100之间的无向图,如何在
线性
时间内找到
最小
生成
树
?
浏览 1
提问于2015-02-01
得票数 1
2
回答
用Kruskal
算法
求图的
最小
生成
树
、
、
、
、
,我需要用Prim的和Kruskal的
算法
找到G的
最小
生成
树
。我很难用Kruskal
算法
找到
最小
生成
树
。我看过很多与Kruskal的图形
算法
相关的视频,但我最终得到了与Prim
算法
相同的图形。 有人能告诉我如何用Kruskal
算法
求图的
最小
生成
树
浏览 1
提问于2019-03-17
得票数 0
回答已采纳
1
回答
给定|E|=99+|V|的
最小
均方时间
算法
、
给出一个无向加权连通图(没有孤立的顶点)求
最小
生成
树
的
线性
算法
,它有V个顶点和|V|+99边,我认为这个解应该是基于Kruskal和除法的,但是到目前为止还没有结果,有什么想法吗?
浏览 3
提问于2021-12-21
得票数 1
3
回答
寻找
最小
瓶颈
生成
树
、
、
、
我知道a是真的,我可以证明,但是找到b和c部分的
算法
正在逃避我。 (c)寻找G的
最小
瓶颈
生成
树
的<e
浏览 7
提问于2012-10-29
得票数 2
回答已采纳
2
回答
求图中MST值的
线性
时间
算法
?
、
是否有一个
线性
О(n+m)时间
算法
仅求给定图G(V,E)的
最小
生成
树
的值r?我们不想找到MST,只是它的边之和。我一直在寻找问题的解决方案,但是Kruskal和Prim的
算法
由于其使用的比较结构(UnionFind(Kruskal)和PQ(Prim))而具有更高的复杂性。
浏览 6
提问于2016-02-04
得票数 1
回答已采纳
4
回答
通用
最小
生成
树
、
、
我正在阅读科门等地的
最小
生成
树
,下面是一般的
最小
生成
树
。在每次迭代
浏览 3
提问于2011-11-16
得票数 2
回答已采纳
2
回答
如何求图中
最小
生成
树
的总数?
、
、
我不想找到所有的
最小
生成
树
,但是我想知道其中有多少
树
,下面是我考虑过的方法: 用prim或kruskal
算法
求出
最小
生成
树
,然后求出所有
生成
树
的权值,当
最小
生成
树
的权重等于
最小
生成
树
的权重时,增加运行计数器我找不到任何方法来求出所有
生成
树
的权重,而且
生成
浏览 4
提问于2012-12-13
得票数 9
回答已采纳
1
回答
在
线性
时间内重新
生成
最小
生成
树
?
、
如果有一个具有V个顶点和E个边的图G,并且我已经知道G的
最小
生成
树
T,然后如果取E中的一些边,并且它们的权重增加了比如说50,那么这些边可能在
最小
生成
树
中,也可能不在
最小
生成
树
中。记住上面的场景,有没有办法在
线性
时间内重新
生成
新的
最小
生成
树
?注意:权重被修改的边数只有5条。
浏览 2
提问于2012-10-22
得票数 2
2
回答
我是否可以使用其他不基于决策
树
的回归类型来像学习梯度增强的弱学习者一样使用它?
、
、
我在想,如果我能像弱学习者一样在梯度提升中使用多项式回归,但我读到决策
树
是用来做这个的,我找不到其他弱学习者可以使用的可能性的东西。
浏览 0
提问于2020-05-26
得票数 2
4
回答
如果边数已知,则创建
最小
生成
树
的时间复杂性
、
、
、
、
假设连通图的边数已知,且每个边的权重是不同的,那么是否可以在
线性
时间内创建
最小
生成
树
?我想到的另一种方法是用
最小
的权重找到边缘;因为边的权重是不同的,这条边将是任何MST的一部分。因为我们不能在
线性
时间内对n-1边这样做。如果我们知道节点的数目
浏览 5
提问于2013-05-31
得票数 3
点击加载更多
扫码
添加站长 进交流群
领取专属
10元无门槛券
手把手带您无忧上云
相关
资讯
什么是最小生成树算法?详述最小生成树算法的原理?用C语言实现最小生成树算法。内附完整代码。
最小生成树-克鲁斯卡尔算法-Kruskal算法
PageRank、最小生成树:ML开发者应该了解的五种图算法
C+图进阶系列之 kruskal和Prim 算法_图向最小生成树的华丽转身
线性回归算法总结
热门
标签
更多标签
云服务器
ICP备案
对象存储
实时音视频
即时通信 IM
活动推荐
运营活动
广告
关闭
领券