3回答
寻找最小瓶颈生成树
、、、
嗨，所以我在做一些测试准备，我需要找出b和c部分。我知道a是真的，我可以证明，但是找到b和c部分的算法正在逃避我。
(b)对于给定的代价c，给出了G最小瓶颈生成树的瓶颈代价不大于c的O(n+m)
浏览 7提问于2012-10-29得票数 2
回答已采纳
2回答
，我需要用Prim的和Kruskal的算法找到G的最小生成树。我很难用Kruskal算法找到最小生成树。我看过很多与Kruskal的图形算法相关的视频，但我最终得到了与Prim算法相同的图形。
有人能告诉我如何用Kruskal算法求图的最小生成树
浏览 1提问于2019-03-17得票数 0
回答已采纳
假设给定一个图G (有n个顶点，m条边)的最小生成树T和一个权重为w的新边e = (u，v)，我们将添加到G上。给出一个有效的算法来寻找图G+e的最小生成树。您的算法应该在O(n)时间内运行，以获得全部积分。从u或v开始Prim或Kruskal alg，直到我们到达给定生成树路径的片段？似乎新的生成树不会因为一条新的边而有太大的变化。
浏览 1提问于2011-01-27得票数 6
2回答
我不想找到所有的最小生成树，但是我想知道其中有多少树，下面是我考虑过的方法：
用prim或kruskal算法求出最小生成树，然后求出所有生成树的权值，当最小生成树的权重等于最小生成树的权重时，增加运行计数器我找不到任何方法来求出所有生成树的权重，而且生成
浏览 4提问于2012-12-13得票数 9
回答已采纳
只是需要确认一下:当我在图上运行Dijkstra的算法时，在最后我会有一个生成树，对吗？(不一定是最小生成树)谢谢
浏览 11提问于2014-02-12得票数 0
回答已采纳
1回答
我们可以通过改变算法来选择最大顶点而不是最小顶点来计算最大生成树吗？
我通过否定边缘和应用普通Prim的最小生成树算法找到了解决方案。
浏览 1提问于2015-07-11得票数 0
3回答
边权值给定时求最小生成树的算法
、、、、
最近有人问我是否可以找到一个算法来计算给定图的最小成本生成树，其中生成树的总成本是边成本的乘积，而不是它们的总和。
有几种算法可以计算正则最小生成树，但我不确定如何针对上面提到的情况调整它们。
浏览 2提问于2010-11-19得票数 3
回答已采纳
2回答
我希望我的最小生成树算法基准与最好的。有人知道在哪里可以找到这些算法的C++实现吗？我大摇大摆地搜索了一下，却什么也没找到。如果这些算法是最好的，那么肯定有一个C++实现吗？--迄今最快的最小生成树算法是由David、Philip和Robert提出的，他发现了一种线性时间随机算法，它是Borůvka算法和反向删除算法的结合。函数
浏览 2提问于2011-02-07得票数 11
回答已采纳
我正在修改一个测试，并遇到了两个问题，与最小生成树在图中，我不确定，并想测试我的答案。
第一个问题是:如果一个图有多个最小生成树，那么Kruskal和Prim的最小生成树算法会生成相同的树吗？我认为它们不一定是因为算法不同而产生的。Kruskal依赖于按权重排序的边，而Prim则不这样做，因此它们可以从不同的顶点开始，从而生成不同的树</
浏览 3提问于2014-04-29得票数 2
回答已采纳
1回答
只有叶子的最小生成树？
、、、
我被要求编写一个算法，在图G中找到最小生成树，但是在图的每个顶点都是生成树T中的一个休假的条件下，如果图中有两个以上的元素，这怎么可能呢？假设G包含顶点a，b和c，生成树可能类似于a，所以在这种情况下，b不是叶。以下是问题的确切措辞
谢谢你的帮助
浏览 1提问于2016-02-14得票数 1
回答已采纳
5回答
它能用来找出最小的吗？如果是这样的话，是怎么做的？
编辑:这不是家庭作业，但我正在尝试理解一个旧的练习考试中的一个问题。
浏览 5提问于2009-12-16得票数 20
回答已采纳
如果最小生成树是贪婪的，为什么Kruskal的算法会找到它呢？最小生成树不是一个全局优化问题吗？贪婪的意义不是在于你有可能找不到最优的解决方案吗？那么，Kruskal如何在贪婪的情况下找到最小生成树呢？
浏览 2提问于2016-12-10得票数 5
算法设计手册中的练习我建议的解决方案(b)是运行DFS，获得最大重量作为平局断路器。然后，每一个后边缘将始终是其周期中的最低加权边。我想知道这是否是一个有效的解决方案。
浏览 0提问于2014-11-05得票数 1
1回答
最小乘积生成树
、、、、
在minimum product spanning tree问题中，树的代价是树中所有边权的乘积，而不是权值之和。你可以假设所有的边都有正的权重。我想得到以下问题的答案。(1)给出了最小乘积生成树与最小权生成树不同的图。
(2)给出了一种计算最小乘积生成树的有效算法。(提示:考虑对数)。
浏览 6提问于2013-04-21得票数 0
3回答
我正在尝试寻找一种有效的方法来检测给定的图G是否有两个不同的最小生成树。我还试图找到一种方法来检查它是否有3种不同的最小生成树。我考虑过的最简单的解决方案是运行Kruskal的算法一次，然后找到最小生成树的总权重。然后，从图中删除一条边，再次运行Kruskal算法，并检查新树的权重是否为原始最小生成树的权重，对图中的每条边也是如
浏览 1提问于2013-05-16得票数 6
2回答
Prim和Kruskal的算法都产生最小生成树。根据cut属性，对于这些算法，树的总成本将是相同的，但这两种算法可能会以相同的总成本给出不同的MST，因为我们在面对多个选择时按字母顺序选择它。例如，我们比较max(source，dest)，对于边A->B和B->C，我们比较来自A->B的A和来自B->C的B。
谢谢
浏览 1提问于2012-11-10得票数 4
云服务器
ICP备案
腾讯会议
云直播
对象存储
腾讯云开发者
