腾讯云
开发者社区
文档
建议反馈
控制台
登录/注册
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
搜索
搜索
关闭
发布
精选内容/技术社群/优惠产品,
尽在小程序
立即前往
文章
问答
(9999+)
视频
沙龙
1
回答
最小
生成
树
我有一个关于图和
最小
生成
树
的作业 假设对于给定的图G1,我们已经计算了
最小
生成
树
T1。现在,G1的一条新边是added.We,将这个带有添加边的新图称为G2。
描述
了一种通过调整G2的T1来有效地计算
最小
生成
树
T2的
算法
。
浏览 1
提问于2013-11-13
得票数 0
1
回答
删除边后包含给定边的
最小
生成
树
、
、
我知道这与max-flow
算法
有关,但我很乐意给你一个提示:我认为
生成
树
是一种完美的匹配。但如何使其
最小
化,使其包含e和适当数量的其他边?
浏览 4
提问于2013-07-08
得票数 2
回答已采纳
2
回答
寻找具有最大
最小
度的
生成
树
、
、
给定一个连通的无向图,寻找具有
最小
最大度的
生成
树
的问题已经得到了很好的研究(M.F¨urer,B.Rahvachari,“近似
最小
度
生成
树
到最优度的1以内”,ACM-SIAM离散
算法
研讨会(SODA),这个问题是NP难的,文献中已经
描述
了一种近似
算法
。 我对以下问题感兴趣-给定一个连通无向图G= (V1,V2,E),找出所有内部节点(非叶子节点)上具有最大
最小
度的
生成
树
。或者有一个
浏览 1
提问于2013-03-18
得票数 3
2
回答
用Kruskal
算法
求图的
最小
生成
树
、
、
、
、
,我需要用Prim的和Kruskal的
算法
找到G的
最小
生成
树
。我很难用Kruskal
算法
找到
最小
生成
树
。我看过很多与Kruskal的图形
算法
相关的视频,但我最终得到了与Prim
算法
相同的图形。 有人能告诉我如何用Kruskal
算法
求图的
最小
生成
树
浏览 1
提问于2019-03-17
得票数 0
回答已采纳
3
回答
寻找
最小
瓶颈
生成
树
、
、
、
我知道a是真的,我可以证明,但是找到b和c部分的
算法
正在逃避我。 (c)寻找G的
最小
瓶颈
生成
树
的<e
浏览 7
提问于2012-10-29
得票数 2
回答已采纳
2
回答
用DFS设置
最小
权反馈边?
算法
设计手册中的练习我建议的解决方案(b)是运行DFS,获得最大重量作为平局断路器。然后,每一个后边缘将始终是其周期中的最低加权边。我想知道这是否是一个有效的解决方案。
浏览 0
提问于2014-11-05
得票数 1
1
回答
一种用于遍历图的线性时间
算法
、
、
、
我正在阅读一本
算法
教科书,以提高我的
算法
技能,但我在这个问题上完全被困住了,这让我很困扰。我认为底层的数据结构是一个图表,但我甚至不知道从哪里开始这个问题。有人能给点见解吗?提出了一个线性时间
算法
,该
算法
可以找到从s到t的路径,从而使最大高度
最小
化。道路可以双向通行。
浏览 3
提问于2013-10-01
得票数 1
4
回答
通用
最小
生成
树
、
、
我正在阅读科门等地的
最小
生成
树
,下面是一般的
最小
生成
树
。在每次迭代
浏览 3
提问于2011-11-16
得票数 2
回答已采纳
1
回答
prims
算法
与boruvka
算法
的区别
、
、
、
我正在学习MST
算法
。我很好奇想要找到prims和boruvka
算法
之间的关键区别,但在线资源除了它们的实现和
算法
之外,没有太多关于它们的内容。如果有人能解释,那将是很大的帮助。谢谢!
浏览 4
提问于2021-07-18
得票数 2
2
回答
如何求图中
最小
生成
树
的总数?
、
、
我不想找到所有的
最小
生成
树
,但是我想知道其中有多少
树
,下面是我考虑过的方法: 用prim或kruskal
算法
求出
最小
生成
树
,然后求出所有
生成
树
的权值,当
最小
生成
树
的权重等于
最小
生成
树
的权重时,增加运行计数器我找不到任何方法来求出所有
生成
树
的权重,而且
生成
浏览 4
提问于2012-12-13
得票数 9
回答已采纳
1
回答
作为运行Dijkstra
算法
的结果的
生成
树
?
、
只是需要确认一下:当我在图上运行Dijkstra的
算法
时,在最后我会有一个
生成
树
,对吗?(不一定是
最小
生成
树
)谢谢
浏览 11
提问于2014-02-12
得票数 0
回答已采纳
1
回答
计算直线
最小
Steiner
树
的最佳
算法
是什么?
、
、
求直线Steiner
最小
树逼近的
算法
有很多。其中包括: 笛子似乎是最有效的
浏览 2
提问于2011-11-24
得票数 2
1
回答
用Prim
算法
求最大
生成
树
、
、
我们可以通过改变
算法
来选择最大顶点而不是
最小
顶点来计算最大
生成
树
吗? 我通过否定边缘和应用普通Prim的
最小
生成
树
算法
找到了解决方案。
浏览 1
提问于2015-07-11
得票数 0
1
回答
用什么
算法
来寻找
最小
生成
森林?
、
、
、
正如维基百科所说: 我们可以用什么
算法
来寻找
最小
生成
森林?
浏览 2
提问于2017-05-16
得票数 2
回答已采纳
1
回答
用igraph寻找Steiner
树
的库
算法
、
我正在尝试实现Kou的
算法
来识别R中的Steiner
树
。Kou的
算法
可以这样
描述
: 用G的最短路(有几条最短路,选择任意一条)代替T‘的每一条边,构造G的子图Gs。求Gs的
最小
生成
树
Ts (如果有
浏览 3
提问于2015-05-06
得票数 13
回答已采纳
3
回答
边权值给定时求
最小
生成
树
的
算法
、
、
、
、
最近有人问我是否可以找到一个
算法
来计算给定图的
最小
成本
生成
树
,其中
生成
树
的总成本是边成本的乘积,而不是它们的总和。 有几种
算法
可以计算正则
最小
生成
树
,但我不确定如何针对上面提到的情况调整它们。
浏览 2
提问于2010-11-19
得票数 3
回答已采纳
1
回答
最小
生成
树
: Kruskal & Prim
我正在修改一个测试,并遇到了两个问题,与
最小
生成
树
在图中,我不确定,并想测试我的答案。 第一个问题是:如果一个图有多个
最小
生成
树
,那么Kruskal和Prim的
最小
生成
树
算法
会
生成
相同的
树
吗?我认为它们不一定是因为
算法
不同而产生的。Kruskal依赖于按权重排序的边,而Prim则不这样做,因此它们可以从不同的顶点开始,从而
生成
不同的
树</
浏览 3
提问于2014-04-29
得票数 2
回答已采纳
1
回答
Kruskal
算法
的变分
、
、
、
您能否按以下结构构造一棵
树
: V_1-v_2-v_3-.-v_n使得
树
中每个节点对应于G中的一个顶点,并且每个节点只有一个子节点,除了叶子。此外,
树
边的总重量被
最小
化。如果使用类似于Kruskal
算法
的
算法
:按升序排序原始图中的所有边的权重。从
最小
权重边开始,如果添加此边不违反上面
描述
的树结构,那么将其添加到最后一棵
树
中,否则,转到下一个。该
算法
能给出权值
最小
的
树
吗?如果没有,是否
浏览 2
提问于2016-01-27
得票数 0
回答已采纳
4
回答
如果
最小
生成
树
是贪婪的,为什么Kruskal的
算法
会找到它呢?
、
如果
最小
生成
树
是贪婪的,为什么Kruskal的
算法
会找到它呢?
最小
生成
树
不是一个全局优化问题吗?贪婪的意义不是在于你有可能找不到最优的解决方案吗?那么,Kruskal如何在贪婪的情况下找到
最小
生成
树
呢?
浏览 2
提问于2016-12-10
得票数 5
1
回答
最小
乘积
生成
树
、
、
、
、
在minimum product spanning tree问题中,
树
的代价是
树
中所有边权的乘积,而不是权值之和。你可以假设所有的边都有正的权重。我想得到以下问题的答案。(1)给出了
最小
乘积
生成
树
与
最小
权
生成
树
不同的图。 (2)给出了一种计算
最小
乘积
生成
树
的有效
算法
。(提示:考虑对数)。
浏览 6
提问于2013-04-21
得票数 0
点击加载更多
扫码
添加站长 进交流群
领取专属
10元无门槛券
手把手带您无忧上云
相关
资讯
什么是最小生成树算法?详述最小生成树算法的原理?用C语言实现最小生成树算法。内附完整代码。
最小生成树-克鲁斯卡尔算法-Kruskal算法
PageRank、最小生成树:ML开发者应该了解的五种图算法
C+图进阶系列之 kruskal和Prim 算法_图向最小生成树的华丽转身
机器学习算法简介(4)回归树和模型树算法简介
热门
标签
更多标签
云服务器
ICP备案
对象存储
实时音视频
即时通信 IM
活动推荐
运营活动
广告
关闭
领券