1回答
我正在尝试在Python3.7中实现kruskal算法。 所以我写了一个程序"bfs“来做广度优先搜索，我想用它来检查在kruskal算法中添加到最小生成树的边是否没有创建圆。并且是为了完整性而发布的。接下来我们有kruskal的算法实现： import networkx as nx V =nx
浏览 24提问于2019-06-04得票数 2
回答已采纳
2回答
我试图将Prim或Kruskal的算法应用于某些情况。据我所知，当图是稠密的时使用Prim (例如:作为具有优先级队列的邻接矩阵作为无序数组，对于E = O(V^2)中的稠密树是很好的。当图稀疏时使用Kruskal (例如:在E = O(V)中作为具有快速排序的邻接列表)。我不确定的是两者之间。例如，一个边数适中的图，是Prim还是
浏览 0提问于2018-11-26得票数 0
回答已采纳
2回答
我知道如何使用Kruskal算法计算MST，我正在考虑这样找到第二最佳最小算法：
这应该是第二好的MST对吧？顺便说一下，我知道有一个主题指出了<
浏览 4提问于2017-04-18得票数 0
回答已采纳
我有一个考试中的问题，我想知道我的方法是否正确。我的解决方案是运行kruskal的算法，然后添加边e如果它不存在，它应该形成一个圆，因为树是n-1个边，所以我们遍历该圆并删除存在于该圆中的最大边(而不是e)。
我的解决方案正确吗？如果是，怎么证明?(附言:我有这个问题的答案，只是想知道我<em
浏览 18提问于2017-01-21得票数 4
回答已采纳
如果这个问题有点宽泛，我很抱歉，但我很难理解如何创建最小成本的生成树。这是用C++编写的，如果这很重要的话。
据我所知，您将使用Kruskal's来选择构建生成树的最低成本边。我的想法是将边缘读入一个小堆中，这样你就可以从顶部移除边缘，从而以最小的成本获得边缘。到目前为止，我只能实现联合查找的minheap和set，我仍然不确定联合查找的目的以及用于创建生成树的排序算法。
浏览 0提问于2011-02-07得票数 1
回答已采纳
2回答
设计一种算法，该算法采用加权图G，并找出代价对非MST边的最小变化，这将导致G的最小生成树发生变化。若要更改MST，我们需要更改非MST边缘s.t的权重。它比它的起始顶点和MST中的结束顶点的路径中的最大边小一个。
因此，我们可以从移动MST的边缘开始，对于每个顶点，检查是否有一个非MST边
浏览 1提问于2012-05-28得票数 1
1回答
我想描述一种算法；G'=(V,E') | E={e'|e' -in E\{e} ,w(e')=< w(e)}
现在我只知道如果有从u到v的路径(u和v是边e的两<em
浏览 0提问于2016-07-05得票数 0
回答已采纳
10回答
它们都有简单的逻辑，相同的最坏情况，唯一的区别是实现可能涉及到一些不同的数据结构。那么决定因素是什么呢？
浏览 0提问于2009-07-28得票数 225
描述一个有效的算法来判断G中是否恰好有2个不同的MST。我们运行Kruskal算法，然后将新MST的边缘着色为蓝色，将其余边缘着色为红色。然后，我使用了另一个
浏览 6提问于2013-03-09得票数 0
回答已采纳
3回答
我正在尝试寻找一种有效的方法来检测给定的图G是否有两个不同的最小生成树。我还试图找到一种方法来检查它是否有3种不同的最小生成树。我考虑过的最简单的解决方案是运行Kruskal的算法一次，然后找到最小生成树的总权重。然后，从图中删除一条边，再次运行Kruskal算法，并检查新树的权重是否
浏览 1提问于2013-05-16得票数 6
给定一个无向加权图，边的实际权重是未知的；相反，每条边都被分类为轻、中或重。所有中边的权重都比任何重边小。
通常，对于同一权重类中的两条边之间的关系一无所知。那么，如何识别这个图的每个MST中必须存在的所有边？以下是我的想法: 1.确定
浏览 1提问于2018-10-20得票数 1
1回答
子图上的MST递归构造
、、、
给定一个图g= (V，E)。将顶点任意划分为两个不相交的集合V1和V2。让E1是V1中具有两个事件点折点的所有边让E2是V2中具有两个事件点折点的所有边让E3是V1中具有一个事件点的所有边V2中的一个
现在构造一个子图(V1，E1)上的MST M1和一个子图( V2，E2)上的MST M2。然后在连接M1和M2的E3中添加最低权重的边</
浏览 0提问于2019-11-19得票数 0
2回答
设e是不在E中的任何边(并且具有权重W(e))。证明或反驳:T U {e}是包含G‘= (V，E U {e})的最小生成树的边集。嗯，对我来说这听起来是真的，所以我决定证明这一点，但我每次都被卡住了……
例如，如果e是具有最小权重的新边，谁能向我们保证T中的边不是以错误的方式选择的，这会阻止我们在没有E-T中其他边的“帮助”的情
浏览 2提问于2013-02-26得票数 7
回答已采纳
2回答
设G(V,E)是一个具有权函数w的无向连通图。我们被授予T，一个G的MST。现在我们将e1, e2, e3从G (也出现在G中的)中删除，得到一个新的图G'。描述了一种有效的G'最小均方搜索算法。
我的</
浏览 2提问于2016-09-13得票数 1
5回答
若F.中G的每个圈至少有一条边，则称边的F⊆E集为⊆反馈边集。(b)设G是一个具有正边权的加权无向图。设计了一种有效的求最小权反馈边缘集的算法.
( a) 最小大小反馈边集：，由于图是不加权的，我
浏览 6提问于2012-05-29得票数 15
我参加了一个面试，面试官问了我一个问题：
我们有一个图G(V，E)，我们可以用prim或kruskal算法找到MST。但是这些算法并没有考虑到G中有“很少”的边，我们如何利用这些信息来提高寻找MST的时间复杂度？我们能在线性时间内找到MST吗？我唯一记得的是，Kruskal的算法在稀疏图中更快，而Prim的算法在真正密集
浏览 5提问于2017-01-25得票数 3
回答已采纳
1回答
设G= (V，E)是一个加权连通无向图，E是e中的任意一条边。给出一个线性时间算法，它决定是否存在包含边e的最小生成树。我设法找到了问题1的一个奇怪的“解决方案”，它似乎是有效的，但我不认为它是线性的：
他们建议对每条边(u，v)使用联合查找和联合(u，v)，使得W(u，v) < W(e)。现在，假设e= (x，y)。= find(y)，那
浏览 1提问于2013-03-02得票数 2
回答已采纳
云服务器
ICP备案
对象存储
腾讯会议
云直播
腾讯云开发者
