只是需要确认一下:当我在图上运行Dijkstra的算法时，在最后我会有一个生成树，对吗？(不一定是最小生成树)谢谢
浏览 11提问于2014-02-12得票数 0
回答已采纳
2回答
我不想找到所有的最小生成树，但是我想知道其中有多少树，下面是我考虑过的方法：
用prim或kruskal算法求出最小生成树，然后求出所有生成树的权值，当最小生成树的权重等于最小生成树的权重时，增加运行计数器我找不到任何方法来求出所有<e
浏览 4提问于2012-12-13得票数 9
回答已采纳
2回答
，我需要用Prim的和Kruskal的算法找到G的最小生成树。我很难用Kruskal算法找到最小生成树。我看过很多与Kruskal的图形算法相关的视频，但我最终得到了与Prim算法相同的图形。
有人能
浏览 1提问于2019-03-17得票数 0
回答已采纳
2回答
给出了图G=(V，E)的两个算法：排序边从最低到最高。为每个边设置了T={}，按照以前的顺序，检查e Set是否没有任何循环。如果是，将e添加到T.，如果它是生成树，则返回T。如果是，请从T.中删除e，如果它是生成树，则返回T。。
这两种算法是否确实返回最小生成树？如果没有，我想看一个反例。
浏览 6提问于2022-07-31得票数 -1
回答已采纳
2回答
Prim和Kruskal的算法都产生最小生成树。根据cut属性，对于这些算法，树的总成本将是相同的，但这两种算法可能会以相同的总成本给出不同的MST，因为我们在面对多个选择时按字母顺序选择它。例如，我们比较max(source，dest)，对于边A->B和B->C，我们比较来自A->B的A和来自B->C的
浏览 1提问于2012-11-10得票数 4
3回答
寻找最小瓶颈生成树
、、、
我知道a是真的，我可以证明，但是找到b和c部分的算法正在逃避我。
解决以下最小瓶颈树，其中边与最大的成本被称为瓶颈。(a) G的每个最小瓶颈生成树是G的最小生成树吗？证明你的主张。(b)对于给定的代价c，给出了G最小瓶颈生成树的瓶颈代价不大于c的<
浏览 7提问于2012-10-29得票数 2
回答已采纳
1回答
我正在学习MST算法。我很好奇想要找到prims和boruvka算法之间的关键区别，但在线资源除了它们的实现和算法之外，没有太多关于它们的内容。如果有人能解释，那将是很大的帮助。谢谢!
浏览 4提问于2021-07-18得票数 2
4回答
通用最小生成树
、、
我正在阅读科门等地的最小生成树，下面是一般的最小生成树。
假设我们有一个连通的无向图G = (V，E)，它有一个加权函数w:E->R，我们希望为G找到一个最小生成树，这里我们用贪婪的方法。这种贪婪策略由以下“泛型”算法捕获，该算法一次生成最小生成树一条
浏览 3提问于2011-11-16得票数 2
回答已采纳
求直线Steiner最小树逼近的算法有很多。其中包括：
RSMT构造和电缆估计的快速查找表技术结果表明，RSMT的长度是矩形最小生成树的3/
浏览 2提问于2011-11-24得票数 2
1回答
我们可以通过改变算法来选择最大顶点而不是最小顶点来计算最大生成树吗？
我通过否定边缘和应用普通Prim的最小生成树算法找到了解决方案。
浏览 1提问于2015-07-11得票数 0
我正在修改一个测试，并遇到了两个问题，与最小生成树在图中，我不确定，并想测试我的答案。
第一个问题是:如果一个图有多个最小生成树，那么Kruskal和Prim的最小生成树算法会生成相同的树吗？我认为它们不一定是因为算法不同而产生的。Kruskal依赖于按权重排序的边，而Pri
浏览 3提问于2014-04-29得票数 2
回答已采纳
3回答
边权值给定时求最小生成树的算法
、、、、
最近有人问我是否可以找到一个算法来计算给定图的最小成本生成树，其中生成树的总成本是边成本的乘积，而不是它们的总和。
有几种算法可以计算正则最小生成树，但我不确定如何针对上面提到的情况调整它们。
浏览 2提问于2010-11-19得票数 3
回答已采纳
给定一个无向加权图，边的实际权重是未知的；相反，每条边都被分类为轻、中或重。所有中边的权重都比任何重边小。
通常，对于同一权重类中的两条边之间的关系一无所知。那么，如何识别这个图的每个MST中必须存在的所有边？以下是我的想法: 1.确定强连通分量的数量。2. MST中必须存在由铰接点组成的边。3.每个连接组件中最亮的边必须存在于MST中。我不
浏览 1提问于2018-10-20得票数 1
2回答
我在分析最小生成树，并想知道排序时间如何影响Kruskal算法的总体时间复杂度？示例：
对于这两种情况，答案仍然是O(e log n)，还是会改变？
浏览 1提问于2014-11-11得票数 2
如果最小生成树是贪婪的，为什么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
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
即时通信 IM
实时音视频活动推荐
腾讯云开发者
