2回答
，我需要用Prim的和Kruskal的算法找到G的最小生成树。我很难用Kruskal算法找到最小生成树。我看过很多与Kruskal的图形算法相关的视频，但我最终得到了与Prim算法相同的图形。
有人能告诉我如何用Kruskal算法求图的最小生成树吗？
浏览 1提问于2019-03-17得票数 0
回答已采纳
3回答
寻找最小瓶颈生成树
、、、
我知道a是真的，我可以证明，但是找到b和c部分的算法正在逃避我。
(c)寻找G的最小瓶颈生成树的算法。
预先感谢任何能帮我的人
浏览 7提问于2012-10-29得票数 2
回答已采纳
2回答
我不想找到所有的最小生成树，但是我想知道其中有多少树，下面是我考虑过的方法：
用prim或kruskal算法求出最小生成树，然后求出所有生成树的权值，当最小生成树的权重等于最小生成树的权重时，增加运行计数器我找不到任何方法来求出所有生成树的权重，而且生成树的数目也可能很大，所以这种方法可能不适合这个问题。由于最小生成树的数目
浏览 4提问于2012-12-13得票数 9
回答已采纳
只是需要确认一下:当我在图上运行Dijkstra的算法时，在最后我会有一个生成树，对吗？(不一定是最小生成树)谢谢
浏览 11提问于2014-02-12得票数 0
回答已采纳
1回答
Kruskal算法的变分
、、、
您能否按以下结构构造一棵树：
V_1-v_2-v_3-.-v_n使得树中每个节点对应于G中的一个顶点，并且每个节点只有一个子节点，除了叶子。此外，树边的总重量被最小化。如果使用类似于Kruskal算法的算法:按升序排序原始图中的所有边的权重。从最小权重边开始，如果添加此边不违反上面描述的树结构，那么将其添加到最后一棵树中，否则，转到下一个。该算法能给出权值最小的树吗？如果没有，是否有可能找到一种<e
浏览 2提问于2016-01-27得票数 0
回答已采纳
1回答
我们可以通过改变算法来选择最大顶点而不是最小顶点来计算最大生成树吗？
我通过否定边缘和应用普通Prim的最小生成树算法找到了解决方案。
浏览 1提问于2015-07-11得票数 0
3回答
边权值给定时求最小生成树的算法
、、、、
最近有人问我是否可以找到一个算法来计算给定图的最小成本生成树，其中生成树的总成本是边成本的乘积，而不是它们的总和。
有几种算法可以计算正则最小生成树，但我不确定如何针对上面提到的情况调整它们。
浏览 2提问于2010-11-19得票数 3
回答已采纳
我正在尝试实现Kou的算法来识别R中的Steiner树。Kou的算法可以这样描述：
用G的最短路(有几条最短路，选择任意一条)代替T‘的每一条边，构造G的子图Gs。求Gs的最小生成树Ts (如果有几棵最小生成<em
浏览 3提问于2015-05-06得票数 13
回答已采纳
2回答
我对Kruskal的算法有一个基本的认识，这就是我发现的：其中不相交的集合是一个数据结构，它实际上很少使用链接列表或森林树方法来导出最小生成树。我想知道的是，不相交集如何影响Kruskal的算法的性能？任何帮助都是值得感激的。
浏览 2提问于2017-08-17得票数 1
我正在修改一个测试，并遇到了两个问题，与最小生成树在图中，我不确定，并想测试我的答案。
第一个问题是:如果一个图有多个最小生成树，那么Kruskal和Prim的最小生成树算法会生成相同的树吗？我认为它们不一定是因为算法不同而产生的。Kruskal依赖于按权重排序的边，而Prim则不这样做，因此它们可以从不同的顶点开始，从而生成不同的树。第二个问题是:如果一个图有多个最小生成树，那么
浏览 3提问于2014-04-29得票数 2
回答已采纳
1回答
基于这个，我发现在O(lg N)中使用两个位来执行RMQ是非常棒的，因为它比分段树更容易编码，并且本文声称它的性能也比其他数据结构更好。
我们做了如下观察:当我们生成所经过的节点的相关间隔时，我们可以从节点p+1开始，覆盖整个区间 p+ 1，y ，以及爬上第一棵树(图2.1)。类似地，我们可以更新表单 x，p-1的所有间隔，方法是从节点p-1开始，爬到第二棵树(图2.2)。采用相同的算法
浏览 4提问于2017-03-09得票数 0
回答已采纳
3回答
我正在尝试寻找一种有效的方法来检测给定的图G是否有两个不同的最小生成树。我还试图找到一种方法来检查它是否有3种不同的最小生成树。我考虑过的最简单的解决方案是运行Kruskal的算法一次，然后找到最小生成树的总权重。然后，从图中删除一条边，再次运行Kruskal算法，并检查新树的权重是否为原始最小生成树的权重，对图中的每条边也是如此。运行时是O(|V||E|log|V|)，这一点都不好，我认为有一种更
浏览 1提问于2013-05-16得票数 6
2回答
我看过下面的prim算法(为了创建一个最小生成树)，我不确定下面代码中的输入值s是什么，我认为G当然应该是发送的图(邻接矩阵或列表图)，我认为值s应该是起点？另外，如果它是start，那么您将以什么方式向以下算法发送起始值？from heapq import heappop, heappush
P, Q = {}, [(0, None, s)] _, p, u = heappop(Q)
浏览 2提问于2012-11-26得票数 2
回答已采纳
1回答
最小乘积生成树
、、、、
在minimum product spanning tree问题中，树的代价是树中所有边权的乘积，而不是权值之和。你可以假设所有的边都有正的权重。我想得到以下问题的答案。(1)给出了最小乘积生成树与最小权生成树不同的图。
(2)给出了一种计算最小乘积生成树的有效算法。(提示:考虑对数)。
浏览 6提问于2013-04-21得票数 0
我正在寻找一些常见数据结构和算法的标准实现，如：
我本来希望有一个Apache通用的-XXX包，但可惜没有？
浏览 0提问于2012-11-13得票数 0
回答已采纳
如果最小生成树是贪婪的，为什么Kruskal的算法会找到它呢？最小生成树不是一个全局优化问题吗？贪婪的意义不是在于你有可能找不到最优的解决方案吗？那么，Kruskal如何在贪婪的情况下找到最小生成树呢？
浏览 2提问于2016-12-10得票数 5
1回答
图中求最小生成树(MST)？
、、、、
给出了一个边上有权的无向图G和2 different最小生成树: T，T‘对于T‘中没有T’的每一个边e，T‘中有一个边e'，它不在T中，所以如果在T中用e'代替e (我们称之为T_new)，那么它仍然是G的最小生成树。我认为我离找到正确的算法太近了，但我坚持了一点：由于T是一棵树，删除e将导致两个分离的组件，那么对于T_new来说，它必须使用连接来自这些不同组件的两个顶点的一条边
浏览 9提问于2021-05-09得票数 1
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
腾讯会议
实时音视频活动推荐
腾讯云开发者
