为什么Kruskal算法必须迭代所有的边？
Kruskal算法是一种用于解决最小生成树问题的贪心算法。它的基本思想是从图中的边集合中选择权重最小的边，并且保证选择的边不会构成环，直到选择的边数达到图中顶点数减一为止。
Kruskal算法必须迭代所有的边的原因是为了确保生成的最小生成树是全局最优解。如果不迭代所有的边，可能会导致生成的最小生成树不是全局最优解，而是局部最优解。
具体来说，如果Kruskal算法在迭代过程中没有考虑到某些边，那么这些边可能会在后续的迭代中被选择，从而形成环路。而形成环路的边不符合最小生成树的定义，因为最小生成树是一个无环的连通子图。
因此，为了确保生成的最小生成树是全局最优解，Kruskal算法必须迭代所有的边，以便在选择边的过程中避免形成环路，并且选择权重最小的边来构建最小生成树。
腾讯云相关产品和产品介绍链接地址：
- 腾讯云计算服务：https://cloud.tencent.com/product/cvm
- 腾讯云数据库：https://cloud.tencent.com/product/cdb
- 腾讯云服务器：https://cloud.tencent.com/product/cvm
- 腾讯云人工智能：https://cloud.tencent.com/product/ai
- 腾讯云物联网：https://cloud.tencent.com/product/iot
- 腾讯云存储：https://cloud.tencent.com/product/cos
- 腾讯云区块链：https://cloud.tencent.com/product/baas
- 腾讯云元宇宙：https://cloud.tencent.com/product/vr
相关·内容
如果最小生成树是贪婪的，为什么Kruskal的算法会找到它呢？最小生成树不是一个全局优化问题吗？贪婪的意义不是在于你有可能找不到最优的解决方案吗？那么，Kruskal如何在贪婪的情况下找到最小生成树呢？
浏览 2提问于2016-12-10得票数 5
3回答
有谁能解释为什么Kruskal产生的树与Dijkstra不同？
我知道kruskal工作在边的非降序上，但是Dijkstra利用优先级队列，但仍然不明白为什么从它们得到的树是不同的？
浏览 2提问于2013-12-05得票数 7
回答已采纳
2回答
我试图将Prim或Kruskal的算法应用于某些情况。据我所知，当图是稠密的时使用Prim (例如:作为具有优先级队列的邻接矩阵作为无序数组，对于E = O(V^2)中的稠密树是很好的。当图稀疏时使用Kruskal (例如:在E = O(V)中作为具有快速排序的邻接列表)。我不确定的是两者之间。例如，一个边数适中的图，
E = O(V log V)
是Prim还是Kruskal？我认为这可能是因为Prim O(E log V)和Kruskal O(E log E)有相似的时间复杂性。
浏览 0提问于2018-11-26得票数 0
回答已采纳
1回答
这是一项消费税：
考虑从加权连通图G中求边的最小权连通子集T的问题。T的权重是T.Give中所有边权之和，是计算最小权连通子集T的有效算法。
以下是我所得到的：
我必须假设权值是正负混合的。只有这两种重量的混合才有意义。
我会先排序边缘，所以负边会排在第一位。
我将考虑使用Kruskal的算法，但应该做一些修改
因为我欢迎负边，所以我会尽可能多地添加负边。
此外，如果不是所有的负边都连接在一起，并且可能需要一些正边作为桥梁，则可能会添加一些正边。
好的，上面是我的想法。但当我想把手弄脏的时候，我就被卡住了。
我怎么能总是记录可能的最小权重集？
例如,
{0
浏览 2提问于2012-05-02得票数 5
回答已采纳
2回答
我在C++ (使用不相交的数据集结构)中实现了Kruskal算法。我正在努力寻找可能的方法，为算法的总运行时间创建更糟的案例场景测试用例。然而，当我试图创建测试用例时，我对如何使该算法产生最坏的情况感到困惑，并想知道这里是否有人知道可能的场景，这将使Kruskal的算法陷入困境。
到目前为止，我认为理论上可能测试Kruskal算法的界限的主要测试是所有权重相同的测试用例。一个例子如下：
4 4
(4, 4) 4 //(4,4) vertex and weight = 4
(4, 4) 4
(4, 4) 4
(4, 4) 4
我最终遇到的是，不管我做什么，如果我试图放慢算法的速度，我就没
浏览 2提问于2014-04-24得票数 2
回答已采纳
如果这个问题有点宽泛，我很抱歉，但我很难理解如何创建最小成本的生成树。这是用C++编写的，如果这很重要的话。
据我所知，您将使用Kruskal's来选择构建生成树的最低成本边。我的想法是将边缘读入一个小堆中，这样你就可以从顶部移除边缘，从而以最小的成本获得边缘。
到目前为止，我只能实现联合查找的minheap和set，我仍然不确定联合查找的目的以及用于创建生成树的排序算法。
如果有任何建议，我将非常感谢。
编辑:我不局限于联合查找、minheap、kruskals和排序算法，也不需要做任何事情。这些只是讲师建议的项目。
浏览 0提问于2011-02-07得票数 1
回答已采纳
Prim和Kruskal的算法用于寻找连通和无向图的最小生成树。为什么不能在有向图上使用它们呢？
浏览 1提问于2014-03-26得票数 23
回答已采纳
10回答
我想知道什么时候应该使用，什么时候使用来找到最小生成树？它们都有简单的逻辑，相同的最坏情况，唯一的区别是实现可能涉及到一些不同的数据结构。那么决定因素是什么呢？
浏览 0提问于2009-07-28得票数 225
2回答
，我需要用Prim的和Kruskal的算法找到G的最小生成树。
我用Prim算法找到了最小生成树。。
我很难用Kruskal算法找到最小生成树。我看过很多与Kruskal的图形算法相关的视频，但我最终得到了与Prim算法相同的图形。
有人能告诉我如何用Kruskal算法求图的最小生成树吗？
浏览 1提问于2019-03-17得票数 0
回答已采纳
1回答
由于Kruskal算法是贪婪的方法，这意味着我们有时可能得不到真正的最小路径。
但是谁能给出一个例子，证明这个算法没有得到最小值？
我不是在寻找复杂性，只是需要一个真正没有得到最优解决方案的案例。
谢谢
浏览 7提问于2019-03-21得票数 0
问题:您需要找到图的最小生成树(即所述图中的边集S，使得S中的边连同相应的顶点形成一棵树；此外，从所有这些集中，S中所有边的代价之和必须最小)。但有个陷阱。给你一个初始的不动边集K，使得K必须包含在S中。
换句话说，找到包含一组固定边开始集的图的一些MST。
我的方法:标准的Kruskal算法，但在任何情况下加入所有顶点，就像固定边集所指出的那样。也就是说，如果K = {1,2}, {4,5}应用Kruskal的算法，而不是最初将每个节点放在自己的单独集合中，而是节点1和2位于相同的集合中，节点4和5位于相同的集合中。
问题是:这个有用吗？是否有证据证明这总是产生正确的结果？如果没有，有人能提
浏览 5提问于2017-02-13得票数 3
回答已采纳
我有一个考试中的问题，我想知道我的方法是否正确。
Input: graph G(V,E),weight function f:E->R and edge e=(u,v).
output: algorithm that finds a minimum spanning tree with edge e in it.
我的解决方案是运行kruskal的算法，然后添加边e如果它不存在，它应该形成一个圆，因为树是n-1个边，所以我们遍历该圆并删除存在于该圆中的最大边(而不是e)。
我的解决方案正确吗？如果是，怎么证明?如果不是，你能告诉我为什么吗？
(附言:我有这个问题的答案，只是想知道我的方法
浏览 18提问于2017-01-21得票数 4
回答已采纳
Kruskal算法在每次迭代时选择最小的边。虽然最终的目标是获得一个MST，但是解决的子问题是什么呢？是为了让森林有最小的重量，也是完全连接起来的吗？
浏览 5提问于2020-07-03得票数 1
回答已采纳
2回答
无向图MST算法(Prim或Kruskal)是有向MST算法(Edmond/Chiu)的一般形式吗？为什么很难找到定向情况下的MST源代码？我们可以使用无向解来获得有向图中的MST吗？
这与以下内容相关：
浏览 6提问于2015-01-16得票数 8
回答已采纳
1回答
当图有多个连通分量时，我不知道如何实现Kruskal算法
根据我对Kruskal算法的理解，它多次向集合中添加最小边。然后，当所有的边都被检查时，它会返回一组最充分的边。
但是，如果我的图是断开的呢？说我有：
A - B - C - D
E - F
假设成本( are )=成本(E)= 1，其余的边大于1。
当我运行Kruskal时，我会得到所有的边的成本，但是我想得到每个连接组件的成本，所以我对所有连接的组件做了一个平均最小的成本。
浏览 0提问于2014-03-07得票数 3
1回答
我正在尝试验证图(G= V，E)的最小生成树(T = V，ET)。有没有一种方法可以验证它，比如return true，否则它就是一个MST，return False？谢谢
浏览 10提问于2021-06-27得票数 0
1回答
我制作了一个c#应用程序，在面板上绘制随机点。我需要根据欧几里得距离把这些点聚在一起。我已经实现了kruskal算法。通常，必须有数量的最小生成树，直至书面数字。例如，当用户想要为3个集群绘制点时，kruskal算法的末尾必须有3个庞大的MST。但我是用不同的方式做的。I做了一个巨大的MST，现在我不得不把MST划分成书面的集群数。例如，=5，集群号2我的kruskal输出是= 0-3:57 1-2:99 1-4:102。
从-到:欧几里得距离
问题是，我不知道应该在哪里削减这些MST来创建集群
浏览 3提问于2019-12-18得票数 0
回答已采纳
算法设计手册中的练习
6-10。4.设G= (V，E)是无向图。一个边的集F⊆E称为反馈边集，如果G的每个圈在F (b)中至少有一个边，设G是一个带正边权的加权无向图。设计了一种有效的求最小权反馈边缘集的算法.
我建议的解决方案(b)是运行DFS，获得最大重量作为平局断路器。然后，每一个后边缘将始终是其周期中的最低加权边。我想知道这是否是一个有效的解决方案。
浏览 0提问于2014-11-05得票数 1
这是来自Wiki的Kruskal的伪代码 algorithm Kruskal(G) is
F:= ∅
for each v ∈ G.V do
MAKE-SET(v)
for each (u, v) in G.E ordered by weight(u, v), increasing do
if FIND-SET(u) ≠ FIND-SET(v) then
F:= F ∪ {(u, v)}
UNION(FIND-SET(u), FIND-SET(v))
return F 我只是想知道为什么只要F.size=|V|-1算法就不能停止？为什么它仍然需
浏览 21提问于2020-11-30得票数 0
1回答
我需要帮助找出工会的问题。
这就是问题所在。
有一个无向连通图，它的n个节点标记为1.n。但是一些边已经断了，切断了图形的连接。找出修复边的最小成本，这样所有节点都可以从彼此之间再次访问。
输入：
n，表示节点总数的int。
边，表示由边连接的节点的整数对的列表。
edgesToRepair，一个列表，其中每个元素都是一个三重奏，分别表示当前边缘被破坏的一对节点以及重复该边缘的成本。
(例如，1、2、12表示重复节点1和2之间的边缘，成本为12)。示例1：
输入:n= 5，边= [1，2，2，3，3，4，4，5，1，5]，
edgesToRepair = [1，2，12，3，4，30，1，5
浏览 2提问于2019-08-13得票数 1
回答已采纳
考虑算法提供的描述。
该算法按升序排序所提供的边缘，并按此顺序处理它们。boost网站上提供的提供了一个通过调用该算法的示例：
std::vector< Edge > spanning_tree;
kruskal_minimum_spanning_tree(g, std::back_inserter(spanning_tree));
运行该算法后，可通过以下方式访问MST的边缘：
std::cout << "Print the edges in the MST:" << std::endl;
for (std::vector< Edge
浏览 6提问于2022-02-20得票数 1
我浏览时发现，文章强烈暗示了不同的迷宫生成算法(随机深度优先搜索、随机Kruskal算法等)。生产具有不同特点的迷宫。这似乎表明，这些算法在所有单解迷宫(矩形网格上的生成树)的集合上产生具有不同概率分布的随机迷宫。
我的问题是：
是对的吗？--也就是说，我看得对吗?这篇文章是对的吗？
，如果是的话，为什么？--我看不出为什么不同的算法会产生不同的发行版。
浏览 30提问于2011-04-05得票数 6
回答已采纳
设G= (V，E)是赋权连通无向图。描述一个有效的算法来判断G中是否恰好有2个不同的MST。
前面我已经解决的问题要简单得多:描述一个有效的算法，它决定在G中是否只有一个MST。
这就是我解决后一个问题的方法：
我们运行Kruskal算法，然后将新MST的边缘着色为蓝色，将其余边缘着色为红色。
然后，我使用了另一个我们已经看到的简单算法(使用Kruskal)，该算法在包含最大数量红色边的图中找到MST -这意味着无论边的颜色如何，它都是图G中的MST，并且每隔一个MST包含的红色边不能超过算法找到的MST。
现在只有一个MST当算法找到了相同的MST (它包含所有的蓝色边)。
这里的另一个问题
浏览 6提问于2013-03-09得票数 0
回答已采纳
1回答
我需要得到一个完整图的MST，其中所有的边都默认为权重3，而且我还得到了有权重1的边。
下面是一个例子
5 4 (N, M)
1 5
1 4
4 2
4 3
Resulting MST = 3 -> 5 -> 1 -> 4 -> 2
如果第一行有总节点数(N)，则1权重边(M)的数量和以下所有行(M)都包含权重为1的边。
我试着构造一个完整的图并将给定边的权值更新为1，但是对于一个包含10^5 1权边的问题来说，空间复杂度太大了。
浏览 4提问于2021-11-28得票数 1
回答已采纳
2回答
下面是我们的CS算法讲师为Kruskal的最小生成树算法编写的伪代码。我想知道MST算法是否是不确定的。给定两条具有相同权重的边，如果在添加到T时，两条边都没有形成循环，算法将如何决定它们之间。当然，如果它是随机的，则无法确定添加到T的确切边的结果？
Given an undirected connected graph G=(V,E)
T=Ø //Empty set, i.e. empty
E'=E
while E'≠Ø do
begin
pick an edge e in E' with minumum
浏览 0提问于2012-05-26得票数 1
回答已采纳
1回答
Kruskal的算法如下：
MST-KRUSKAL(G,w)
1. A={}
2. for each vertex v∈ G.V
3. MAKE-SET(v)
4. sort the edges of G.E into nondecreasing order by weight w
5. for each edge (u,v) ∈ G.E, taken in nondecreasing order by weight w
6. if FIND-SET(u)!=FIND-SET(v)
7. A=A U {(u,v)}
8. Union
浏览 4提问于2015-04-10得票数 8
回答已采纳
2回答
我不想找到所有的最小生成树，但是我想知道其中有多少树，下面是我考虑过的方法：
用prim或kruskal算法求出最小生成树，然后求出所有生成树的权值，当最小生成树的权重等于最小生成树的权重时，增加运行计数器。
我找不到任何方法来求出所有生成树的权重，而且生成树的数目也可能很大，所以这种方法可能不适合这个问题。由于最小生成树的数目是指数的，将它们计算起来不是一个好主意。
所有的重量都是正数。
我们还可以假设，在图中不会出现超过三次的权重。
顶点的数目将小于或等于40,000。
边数将小于或等于100,000。
图中只有一个最小生成树，其中顶点的权重是不同的。我
浏览 4提问于2012-12-13得票数 9
回答已采纳
2回答
给出了图G=(V，E)的两个算法：
第一：
排序边从最低到最高。为每个边设置了T={}，按照以前的顺序，检查e Set是否没有任何循环。如果是，将e添加到T.，如果它是生成树，则返回T。
二：
排序边从最高到最低。为每个边e设置T=E，检查T{e}是否是连通图。如果是，请从T.中删除e，如果它是生成树，则返回T。。
这两种算法是否确实返回最小生成树？如果没有，我想看一个反例。
浏览 6提问于2022-07-31得票数 -1
回答已采纳
2回答
问题：
形成一个网络，即所有的基础都可以从每个基地到达。一个基地可以从另一个基地，如果有一个通道的隧道连接基地。基是基于具有整数坐标的二维平面而设的.在两个基之间建造隧道的费用是坐标(x1，y1)和(x2，y2)，其费用是min{ x1-x2\x，\y1-y2 }。
形成网络的最低成本是多少？
1 ≤ N ≤ 100000 // Number of bases
-10^9 ≤ xi,yi ≤ 10^9
典型的Kruskal的最小生成树 implementation.But u不能存储(10^5)^2边。那么，我应该如何建立我的成本矩阵，如何制作一个图表，以便我可以应用Kruskal算法？
浏览 2提问于2014-12-19得票数 0
2回答
为什么E支配v？
、、
分析了Kruskal算法的运行时间，提出了O(ElogE+Elogv+v)算法。
我问我的教授，他说如果图很稀疏，很多孤立的顶点V支配E，如果没有，那么E支配V，我不明白为什么？我可以给出一个例子，图不是稀疏的，但V仍然大于E。
有人能帮我澄清这种混乱吗？
浏览 10提问于2014-03-03得票数 1
回答已采纳
1回答
设G= (V，E)是一个加权连通无向图，E是e中的任意一条边。给出一个线性时间算法，它决定是否存在包含边e的最小生成树。
我设法找到了问题1的一个奇怪的“解决方案”，它似乎是有效的，但我不认为它是线性的：
他们建议对每条边(u，v)使用联合查找和联合(u，v)，使得W(u，v) < W(e)。现在，假设e= (x，y)。现在如果find(x) != find(y)，那么x和y是不相连的，而W( e )肯定是Kruskal算法要检查的下一个权重，所以肯定存在一个包含边e的MST。
另一方面，如果find(x) = find(y)，那么如果我们运行Kruskal算法到这一点，x和y肯定是相连
浏览 1提问于2013-03-02得票数 2
回答已采纳
4回答
我在课本上偶然发现了这个问题：
“一般来说，Prim算法、Kruskal算法和Dijkstra算法的时间复杂度取决于什么？”
a.图中的顶点数。
b.图中的边数。
两者都是关于图中顶点和边的数目。
解释你的选择。
因此，根据维基百科Prim，Kruskal和Dijkstra的算法，最坏的情况时间复杂度分别是O(ElogV)，O(ElogV)和O(E+VlogV)。所以我想答案是c？但是为什么呢？
浏览 5提问于2012-08-09得票数 2
我试图理解为什么Prim和Kruskal在处理稀疏和密集图时具有不同的时间复杂性。在使用了几个演示如何工作的applet之后，我仍然对图的密度如何影响算法感到有点困惑。我希望有人能给我一个正确的方向。
浏览 1提问于2010-01-06得票数 9
3回答
假设我们有一个数组
[37, 20, 16, 8, 5, 5, 3, 0]
我可以使用什么算法来指定分区的数量并将数组分解到它们中。
对于两个分区，应该是
[37] and [20, 16, 8, 5, 5, 3, 0]
对于3，它应该是
[37],[20, 16] and [8, 5, 5, 3, 0]
我可以通过简单地用右和左数字减去元素就可以将它们分解，但这并不能确保分区的正确数量。有什么想法吗？
我的代码是ruby的，但是任何语言/algo/伪代码都足够了。
这是维克拉姆算法的红宝石代码
def partition(arr,clusters)
# Return same array
浏览 0提问于2013-12-28得票数 0
回答已采纳
2回答
我试图从加权无向图中求出第二次最佳最小跨越3。我知道如何使用Kruskal算法计算MST，我正在考虑这样找到第二最佳最小算法：
步骤：
对所有的图形边进行排序。
用Kruskal计算MST
从不在第一个MST中的图中获取最小权重边，并将其添加到MST (现在MST有了一个循环)
消除新成形循环中的最大重量边。
这应该是第二好的MST对吧？
顺便说一下，我知道有一个主题指出了一个算法，它在每个MST边之间迭代，然后在图上运行Kruskal，而没有选择边缘，我只是在问我的算法是否有效。
浏览 4提问于2017-04-18得票数 0
回答已采纳
我们知道原始的图和原始的MST。现在我们改变图中一条边的权重。除了Prim和Kruskal之外，有没有办法从旧的MST生成新的MST？
浏览 0提问于2012-11-18得票数 4
2回答
生成随机对称加权邻接矩阵
、、、
我试着用一个成本邻接矩阵来测试Prim和Kruskal算法的实现。我在图中的顶点和边的数量上生成这些矩阵。它不一定是连通图。
到目前为止，我的情况如下：
final static int infinity = 2000000000;
public static int[][] genAdjMat(int V, int E) {
int[][] a = new int[V][V];
int e = E;
for(int i = 0; i < V; i++) {
for(int j = i; j < V; j++) {
浏览 4提问于2016-12-02得票数 2
回答已采纳
我参加了一个面试，面试官问了我一个问题：
我们有一个图G(V，E)，我们可以用prim或kruskal算法找到MST。但是这些算法并没有考虑到G中有“很少”的边，我们如何利用这些信息来提高寻找MST的时间复杂度？我们能在线性时间内找到MST吗？
我唯一记得的是，Kruskal的算法在稀疏图中更快，而Prim的算法在真正密集的图中更快。但我无法回答他如何利用关于边数的先验知识在线性时间内生成MST。
如有任何见解或解决方案，将不胜感激。
浏览 5提问于2017-01-25得票数 3
回答已采纳
2回答
具有MST的图(正权重边)如果某些边，e被修改为新值，那么更新MST而不完全重新生成它的最佳方法是什么？我认为这可以在线性时间内完成。此外，我似乎需要一个不同的算法，基于是否1) e已经是MST的一部分，以及2)新边e是否比原始边更大或更小
浏览 1提问于2012-03-30得票数 21
7回答
如何找到最大生成树？
、、、
与Kruskal的最小生成树算法相反的算法对它有效吗？我的意思是，选择每一步的最大权重(边)？
有没有找到最大生成树的其他想法？
浏览 4提问于2011-02-14得票数 64
回答已采纳
2回答
Prim和Kruskal的算法都产生最小生成树。根据cut属性，对于这些算法，树的总成本将是相同的，但这两种算法可能会以相同的总成本给出不同的MST，因为我们在面对多个选择时按字母顺序选择它。例如，我们比较max(source，dest)，对于边A->B和B->C，我们比较来自A->B的A和来自B->C的B。
谢谢
浏览 1提问于2012-11-10得票数 4
所以我正在教自己一些图算法，现在在Kruskal上，并且了解到推荐使用union-find，所以检查添加边是否只需要O(Log )时间。出于实际目的，我明白为什么您会想要这样做，但严格地使用Big表示法，这样做真的会影响最坏情况的复杂性吗？
我的推理是:如果我们没有进行联合查找，而是做了一个DFS来检查周期，那么它的运行时将是O(E+V)，对于O(V^2 + VE)的运行时，您必须执行V次。它比联合查找更多，这将是O(V * LogV)，但是Kruskal的大部分复杂性来自于删除优先级队列E时间的最小元素，即O(E * logE)，这是大O的答案。我也看不到空间优势，因为联合查找占用了O(V)
浏览 9提问于2015-08-16得票数 5
回答已采纳
2回答
查找MST的所有临界边缘
、、、
我有一个问题来自罗伯特·塞奇威克关于算法的书。
临界边。是一种从图中删除会导致MST权重增加的MST边缘，称为临界边缘。说明如何在图中找到与E log E成正比的所有临界边。注意:这个问题假定边的权重不一定是不同的(否则MST中的所有边都是关键的)。
请提出解决这个问题的算法。
我能想到的一种方法是在E.V中完成任务，我的方法是运行kruskal的算法。
但是，每当我们遇到一个边缘，其插入在MST中创建一个循环，如果该周期已经包含一个具有相同边缘权重的边缘，那么，已经插入的边缘将不是临界边缘(否则所有其他MST边缘都是临界边缘)。
这个算法正确吗？我如何扩展这个算法，以便及时完成E日志
浏览 0提问于2013-03-30得票数 8
回答已采纳
2回答
给定一个带权的无向连通图。w:E->{1,2,3,4,5,6,7} -意味着只有7个权重。我需要使用O(n+m)中的Prim算法和O( m*a(m，n))中的Kruskal算法找到一棵生成树。
我不知道如何做到这一点，真的需要一些指导，如何权重可以帮助我在这里。
浏览 4提问于2012-05-28得票数 0
1回答
带度约束的最小生成树
、、、、
我必须解决这个问题：
给出了一个加权连通无向图G=( V，E)和顶点u，给出了求G的MST的算法，使得u的度最小，算法的输出T为最小生成树T‘，最小生成树T’为T中u小于或等于u在T‘中的度。
我考虑了这个算法(在googling搜索之后，我找到了类似问题的解决方案)：
临时删除顶点u。
对于每个得到的连接组件C1，…，Cm使用例如Kruskal或Prim的算法找到MST。
重新添加顶点u，并为每个词添加1和Ci之间最便宜的边。
编辑：
我知道这个算法可能会产生错误的MST (见@AndyG注释)，所以我想到了另一个：
设k是G中每两个权重之间的最小增量，并将0
浏览 10提问于2015-05-17得票数 2
回答已采纳
只是需要确认一下:当我在图上运行Dijkstra的算法时，在最后我会有一个生成树，对吗？(不一定是最小生成树)
那么，Dijkstra和PRIM/Kruskal的区别在于，后两种算法将返回最小生成树？
谢谢
浏览 11提问于2014-02-12得票数 0
回答已采纳
3回答
我正在尝试寻找一种有效的方法来检测给定的图G是否有两个不同的最小生成树。我还试图找到一种方法来检查它是否有3种不同的最小生成树。我考虑过的最简单的解决方案是运行Kruskal的算法一次，然后找到最小生成树的总权重。然后，从图中删除一条边，再次运行Kruskal算法，并检查新树的权重是否为原始最小生成树的权重，对图中的每条边也是如此。运行时是O(|V||E|log|V|)，这一点都不好，我认为有一种更好的方法。
任何建议都将是有帮助的，提前谢谢
浏览 1提问于2013-05-16得票数 6
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
腾讯会议
实时音视频活动推荐
腾讯云开发者
