1回答
我们可以通过改变算法来选择最大顶点而不是最小顶点来计算最大生成树吗？
我通过否定边缘和应用普通Prim的最小生成树算法找到了解决方案。
浏览 1提问于2015-07-11得票数 0
2回答
，我需要用Prim的和Kruskal的算法找到G的最小生成树。我很难用Kruskal算法找到最小生成树。我看过很多与Kruskal的图形算法相关的视频，但我最终得到了与Prim算法相同的图形。
有人能
浏览 1提问于2019-03-17得票数 0
回答已采纳
3回答
寻找最小瓶颈生成树
、、、
我知道a是真的，我可以证明，但是找到b和c部分的算法正在逃避我。
解决以下最小瓶颈树，其中边与最大的成本被称为瓶颈。(a) G的每个最小瓶颈生成树是G的最小生成树吗？证明你的主张。(b)对于给定的代价c，给出了G最小瓶颈生成树的瓶颈代价不大于c的<
浏览 7提问于2012-10-29得票数 2
回答已采纳
4回答
通用最小生成树
、、
我正在阅读科门等地的最小生成树，下面是一般的最小生成树。
假设我们有一个连通的无向图G = (V，E)，它有一个加权函数w:E->R，我们希望为G找到一个最小生成树，这里我们用贪婪的方法。这种贪婪策略由以下“泛型”算法捕获，该算法一次生成最小生成树一条
浏览 3提问于2011-11-16得票数 2
回答已采纳
2回答
我不想找到所有的最小生成树，但是我想知道其中有多少树，下面是我考虑过的方法：
用prim或kruskal算法求出最小生成树，然后求出所有生成树的权值，当最小生成树的权重等于最小生成树的权重时，增加运行计数器我找不到任何方法来求出所有<e
浏览 4提问于2012-12-13得票数 9
回答已采纳
求直线Steiner最小树逼近的算法有很多。其中包括：
RSMT构造和电缆估计的快速查找表技术结果表明，RSMT的长度是矩形最小生成树的3/
浏览 2提问于2011-11-24得票数 2
只是需要确认一下:当我在图上运行Dijkstra的算法时，在最后我会有一个生成树，对吗？(不一定是最小生成树)谢谢
浏览 11提问于2014-02-12得票数 0
回答已采纳
3回答
边权值给定时求最小生成树的算法
、、、、
最近有人问我是否可以找到一个算法来计算给定图的最小成本生成树，其中生成树的总成本是边成本的乘积，而不是它们的总和。
有几种算法可以计算正则最小生成树，但我不确定如何针对上面提到的情况调整它们。
浏览 2提问于2010-11-19得票数 3
回答已采纳
我正在修改一个测试，并遇到了两个问题，与最小生成树在图中，我不确定，并想测试我的答案。
第一个问题是:如果一个图有多个最小生成树，那么Kruskal和Prim的最小生成树算法会生成相同的树吗？我认为它们不一定是因为算法不同而产生的。Kruskal依赖于按权重排序的边，而Pri
浏览 3提问于2014-04-29得票数 2
回答已采纳
1回答
当我看到时，这个问题突然浮现在我的脑海中。为了简单起见，我们可以将讨论限制在无向、加权、连通图上。显然，如果从图中选择任意节点作为源，Dijkstra不能保证生成MST。然而，它是否保证在一个无向、加权、连通图中必须存在一个节点，如果我们选择它作为源并应用Dijkstra的算法，它将为该图生成一个MST？也许你可以给出一个证据或者一个反例。谢谢!
浏览 1提问于2020-12-16得票数 2
回答已采纳
2回答
考虑到我们试图将prim算法应用于不连通图上。考虑这个不连通图有顶点a，b，c和d，其中这个顶点d是不连通的。现在我需要检查我的理解，如果我们在这个不连通图上应用prim算法，算法不会到达顶点d，因此只返回a，b和c点的MST。那么，这个假设是对的吗？
浏览 4提问于2020-03-29得票数 0
如果最小生成树是贪婪的，为什么Kruskal的算法会找到它呢？最小生成树不是一个全局优化问题吗？贪婪的意义不是在于你有可能找不到最优的解决方案吗？那么，Kruskal如何在贪婪的情况下找到最小生成树呢？
浏览 2提问于2016-12-10得票数 5
1回答
最小乘积生成树
、、、、
在minimum product spanning tree问题中，树的代价是树中所有边权的乘积，而不是权值之和。你可以假设所有的边都有正的权重。我想得到以下问题的答案。(1)给出了最小乘积生成树与最小权生成树不同的图。
(2)给出了一种计算最小乘积生成树的有效算法。(提示:
浏览 6提问于2013-04-21得票数 0
3回答
我正在尝试寻找一种有效的方法来检测给定的图G是否有两个不同的最小生成树。我还试图找到一种方法来检查它是否有3种不同的最小生成树。我考虑过的最简单的解决方案是运行Kruskal的算法一次，然后找到最小生成树的总权重。然后，从图中删除一条边，再次运行Kruskal算法</
浏览 1提问于2013-05-16得票数 6
1回答
图中求最小生成树(MST)？
、、、、
给出了一个边上有权的无向图G和2 different最小生成树: T，T‘对于T‘中没有T’的每一个边e，T‘中有一个边e'，它不在T中，所以如果在T中用e'代替e (我们称之为T_new)，那么它仍然是G的最小生成树。我认为我离找到正确的算法太近了，但我坚持了一点：由于T是一棵树</
浏览 9提问于2021-05-09得票数 1
3回答
我目前正在优化电网规划，而MST没有很好地解决这个问题，因为如果到主电网的连接是一个辐射点，所有的电力都必须流经一条边，并将经过很长的“电气距离”到达每个耗电量点。我正在研究的问题可能是最小化MW*distance或有功功率矩，但这会产生一个非线性问题。
所以我要找的是一个最小的生成树(不是最优的，只是最有效的)，它最小化到树根的最大电气距离(通过图的</
浏览 1提问于2013-06-27得票数 6
4回答
用Kruskal算法可以在最坏的情况下找到O(E log*V)中的最小瓶颈生成树。这是因为每个最小生成树都是最小瓶颈生成树。
但我被课程的面试问题困住了。在最坏的情况下，如何在线性时间内找到最小瓶颈生成树。请注意，我们可以假设在最坏的情况下，我们可以在线性时间内计算n个键<e
浏览 23提问于2014-04-05得票数 5
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
实时音视频
即时通信 IM活动推荐
腾讯云开发者
