2回答
，我需要用Prim的和Kruskal的算法找到G的最小生成树。我很难用Kruskal算法找到最小生成树。我看过很多与Kruskal的图形算法相关的视频，但我最终得到了与Prim算法相同的图形。
有人能告诉我如何用Kruskal算法求图的最小生成树吗？
浏览 1提问于2019-03-17得票数 0
回答已采纳
请告诉我如何计算Kruskal定理的时间复杂度的步骤？我知道Kruskal算法的算法，但不知道伪码和时间复杂度的计算。Kruskal算法的复杂度为O(E log E) = O(E log V) (维基百科)。但我不知道如何计算..
浏览 1提问于2014-04-14得票数 0
1回答
设计了一种在线性时间(O(n + m))内求G最小生成树的算法。
Kruskal(G) sort all edges in non-decreasingPARENT FIND() ≔ ()
≔
while ≠ P
浏览 2提问于2016-03-01得票数 4
回答已采纳
2回答
我试图将Prim或Kruskal的算法应用于某些情况。据我所知，当图是稠密的时使用Prim (例如:作为具有优先级队列的邻接矩阵作为无序数组，对于E = O(V^2)中的稠密树是很好的。当图稀疏时使用Kruskal (例如:在E = O(V)中作为具有快速排序的邻接列表)。我不确定的是两者之间。例如，一个边数适中的图，是Prim还是Kruskal？我认为这可能是因为Prim O(E log V)和Kruskal O(E log E)有相似的时间复杂性。
浏览 0提问于2018-11-26得票数 0
回答已采纳
2回答
给出了图G=(V，E)的两个算法：排序边从最低到最高。为每个边设置了T={}，按照以前的顺序，检查e Set是否没有任何循环。如果是，将e添加到T.，如果它是生成树，则返回T。这两种算法是否确实返回最小生成树？如果没有，我想看一个反例。
浏览 6提问于2022-07-31得票数 -1
回答已采纳
1回答
在我参加的编程课上，我们学习了Bellman-Ford SSSP和Djikstra的SSSP，我们了解到Bellman-Ford是基于Kruskal的最小生成树算法的，而Djikstra是基于Prim的最小生成树算法的我们还被告知要记住，Bellman和Kruskal在全球范围内运作，因为您选择最小的边缘权重，而不考虑先前选择的节点。对于Kruskal的算法，我能理解为什么我们可以认为这是全局的，因为你实际上只是选择最轻或最小的边缘重量。但是对于Bellman的算法，我
浏览 1提问于2015-05-11得票数 2
2回答
我在C++ (使用不相交的数据集结构)中实现了Kruskal算法。我正在努力寻找可能的方法，为算法的总运行时间创建更糟的案例场景测试用例。然而，当我试图创建测试用例时，我对如何使该算法产生最坏的情况感到困惑，并想知道这里是否有人知道可能的场景，这将使Kruskal的算法陷入困境。到目前为止，我认为理论上可能测试Kruskal算法的界限的主要测试是所有权重相同的测试用例。一个例子如下：(4, 4) 4 //(4,4) ve
浏览 2提问于2014-04-24得票数 2
回答已采纳
10回答
我想知道什么时候应该使用，什么时候使用来找到最小生成树？它们都有简单的逻辑，相同的最坏情况，唯一的区别是实现可能涉及到一些不同的数据结构。那么决定因素是什么呢？
浏览 0提问于2009-07-28得票数 225
2回答
我知道如何使用Kruskal算法计算MST，我正在考虑这样找到第二最佳最小算法：
这应该是第二好的MST对吧？顺便说一下，我知道有一个主题指出了一个算法，它在每个MST边之间迭代，然后在图上运行Kruskal，而没有选择边缘，我只是在问我的算法是否有效。
浏览 4提问于2017-04-18得票数 0
回答已采纳
4回答
我在课本上偶然发现了这个问题：
a.图中的顶点数。两者都是关于图中顶点和边的数目。因此，根据维基百科Prim，Kruskal和Dijkstra的算法，最坏的情况时间复杂度分别是O(ElogV)，O(ElogV)和O(E+VlogV)。所以我想答案是c？但是为什么呢？
浏览 5提问于2012-08-09得票数 2
1回答
我必须生成简单的无向图，在上面测试我的Kruskal算法。struct connection node1; edge_value;现在，我需要生成大量的这些连接，以便在上面测试KruskalKruskal的算法没有这一代人那么难，可能是因为这是我第一次面对图形。
浏览 0提问于2012-03-09得票数 0
据我所知，您将使用Kruskal's来选择构建生成树的最低成本边。我的想法是将边缘读入一个小堆中，这样你就可以从顶部移除边缘，从而以最小的成本获得边缘。到目前为止，我只能实现联合查找的minheap和set，我仍然不确定联合查找的目的以及用于创建生成树的排序算法。
如果有任何建议，我将非常感谢。编辑:我不局限于联合查找、minheap、kruskals和排序算法，也不需要做任何事情。这些只是讲师建议的项目。
浏览 0提问于2011-02-07得票数 1
回答已采纳
1回答
由于Kruskal算法是贪婪的方法，这意味着我们有时可能得不到真正的最小路径。我不是在寻找复杂性，只是需要一个真正没有得到最优解决方案的案例。
浏览 7提问于2019-03-21得票数 0
2回答
设计一种算法，该算法采用加权图G，并找出代价对非MST边的最小变化，这将导致G的最小生成树发生变化。若要更改MST，我们需要更改非MST边缘s.t的权重。
浏览 1提问于2012-05-28得票数 1
2回答
我正在寻找一种算法，它将连接大量的地理坐标(100-1000)，在它们之间创建最短的路径，从任何地方开始，在其他任何地方完成。我和Python一起工作。我已经研究了现有的算法，我的问题类似于旅行推销员，但它需要我定义一个起点，并将在最后回到这个点。，我将带一个优步到任何起点，从任何其他终点回家。我想要的是涵盖所有的点，同时尽可能少走。Prim和Kruskal的算法似乎找到了很好的起点和终点，但它们创建了一棵树，而不是TSP那样的优化步行路线。Prim算法：Kruskal<em
浏览 8提问于2019-02-27得票数 1
回答已采纳
1回答
在讨论聚类时，他告诉我们，K-均值聚类算法是应用最广泛的算法.我之前还使用了Kruskal的聚类算法，这是一种非常有效的基于路径压缩和基于秩的联合算法。什么使K-的意思比Kruskal的算法更好？
浏览 2提问于2020-06-01得票数 3
回答已采纳
1回答
我已经实现了kruskal算法。通常，必须有数量的最小生成树，直至书面数字。例如，当用户想要为3个集群绘制点时，kruskal算法的末尾必须有3个庞大的MST。但我是用不同的方式做的。例如，=5，集群号2我的kruskal输出是= 0-3:57 1-2:99 1-4:102。问题是，我不知道应该在哪里削减这些MST来创建集群
浏览 3提问于2019-12-18得票数 0
回答已采纳
1回答
当图有多个连通分量时，我不知道如何实现Kruskal算法但是，如果我的图是断开的呢？当我运行Kruskal时，我会得到所有的边的成本，但是我想得到每个连接组件的成本，所以我对所有连接的组件做了一个平均最小的成本。
浏览 0提问于2014-03-07得票数 3
1回答
在加权无向图中，我需要修改Kruskal的算法，以求MST有条件，因为它在O(m log n)时间内包含给定的边'e‘。我怎么能这么做？
浏览 3提问于2022-03-01得票数 1
回答已采纳
1回答
最大权重欧几里德生成树
、、、、
通过运行kruskal算法(只需改变边函数并首先考虑最大权重边)，可以找到最大生成树。我感兴趣的是寻找最大权重的欧几里德生成树。有没有比kruskal更好的算法(更好的最坏情况下的运行时间)来找到这样的生成树？
浏览 10提问于2013-04-11得票数 5
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
腾讯会议
实时音视频活动推荐
腾讯云开发者
