在最小生成树中，我们需要在移动到其他边之前连接具有最小权重的边。为了执行连接，我们使用UF DS的联合操作，它连接不相交数据集的代表元素。是否可以保证代表性元素将是我们打算加入的具有最小边权重的节点？连接很可能发生在要连接
浏览 27提问于2021-05-01得票数 2
2回答
我正在尝试使用Kruskal的最小生成树算法进行K-Means聚类。我最初的设计是运行输入的全长Kruskal算法并生成MST，然后删除最后的k-1条边(或者相当于k-1条最昂贵的边)。当然，这与运行Kruskal算法并在它添加最后k-1条边之前停止它是相同的。
我想使用第二种策略，即不是运行全长Kruskal算法，而是在到目前
浏览 0提问于2012-12-14得票数 0
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
描述一个有效的算法来判断G中是否恰好有2个不同的MST。我们运行Kruskal算法，然后将新MST的边缘着色为蓝色，将其余边缘着色为红色。然后，我使用了另一个我们已经看到的简单算法(使用Kruskal)，该算法在
浏览 6提问于2013-03-09得票数 0
回答已采纳
Prim和Kruskal的算法用于寻找连通和无向图的最小生成树。为什么不能在有向图上使用它们呢？
浏览 1提问于2014-03-26得票数 23
回答已采纳
给定具有成本边x或y(其中x小于y且都是正整数)的无向连通图，在O(V+E)中找到MST
这个想法涉及到使用两次DFS运行，并将权重较低的节点折叠为超级节点(在第一次DFS运行之后)，但我不完全确定。任何帮助都是非常感谢的。我已经在几个答案中看到了这样的解决方案，但在任何地方都找不到对它的解释。
浏览 15提问于2018-02-27得票数 0
如果这个问题有点宽泛，我很抱歉，但我很难理解如何创建最小成本的生成树。这是用C++编写的，如果这很重要的话。如果有任何建议，我将非常感谢。这些
浏览 0提问于2011-02-07得票数 1
回答已采纳
3回答
查找连接所有节点的最短路径集
、、、、
我在二维坐标空间中有一组点。这可能听起来像旅行推销员的问题，但它是不同的。我不是在寻找一个周期，它将访问每个点一次并且只有一次。我只需要每个点连接到至少一个其他点，这样集合中的所有点至少间接地彼此连接，所选连接的长度之和将被最小化。因此，它应该是非循环的，以最小化连接
浏览 6提问于2020-01-31得票数 1
2回答
这就是我的问题:我需要一个算法，给定一组n坐标点，(x;y)是连接所有点的最短路径，没有任何限制，这意味着一个点可以链接到任意数量的其他点。解决问题的第一个想法是，对于每个不连通点，找到最近的点并链接到它，然后从未链接的点列表中删除这两个点，然后重新开始，直到没有更多不喜欢的点。在这个阶段，你已经创造了几个接近点的块。然后你把这些街区连接起来，找出它们之间最短的距离。这个方法<em
浏览 0提问于2015-11-30得票数 0
回答已采纳
我正在学习Kruskal的算法，我遇到了几种不同的实现，我想知道它们之间的权衡可能是什么。两种实现方式如下：
实现1-将图中的所有边放入优先级队列PQ -从PQ中移除最小边e-如果e连接2个先前未连接的图组件(使用Union Find数据结构测试)，则将其添加到MST -重复，直到MST中的边数等于图中顶点的总
浏览 0提问于2015-12-15得票数 0
证明了kruskal算法生成的ST是MST。我们可以叫它ST1。现在的问题是:证明不存在其他ST，其最大加权边小于ST1中的最大加权边。
浏览 42提问于2019-09-26得票数 0
回答已采纳
1回答
虚线边将被添加，以从这棵树构建一个完整的图。跨T作为其唯一MST的最小权重完整图G如下：1)找出图中包含权重w_max的最大MST边和不包含其他MST边的割集。所有其他边缘都必须是w_max + 1。证明:假设相反；我们可以用另一条边替换(2-3)，并
浏览 2提问于2015-01-05得票数 3
回答已采纳
10回答
我想知道什么时候应该使用，什么时候使用来找到最小生成树？它们都有简单的逻辑，相同的最坏情况，唯一的区别是实现可能涉及到一些不同的数据结构。那么决定因素是什么呢？
浏览 0提问于2009-07-28得票数 225
1回答
我已经写了一个使用Prim方法解决MST的代码。我读到这种实现(使用优先级队列)应该有O(E + VlogV) = O(VlogV)，其中E是边的数量，V是边的数量，但当我查看我的代码时，它看起来不是这样的。在我看来，运行时间是这样的：
while循环需要O(E)次(直到我们遍历所有的边)，在该循环中，我们从Q中提取一个元素，这需要O(logE)时间。100][100] = { 0 }; //ad
浏览 2提问于2009-11-19得票数 3
回答已采纳
我在解决一个关于最小生成树的问题时遇到了一些麻烦。因此，图中的每个节点都是一个城市，并且有可能将两个节点连接在一起，这就是在两个城市之间修建一条道路的成本。现在，棘手的部分来了:每个城市(节点)可以有一个机场，每个机场都有一个时间成本(如果你决定建造它)。如果两个城市都有机场，你可以使用机场在两个城市之间旅行。现在，我必须计算建造道路和机场<em
浏览 3提问于2017-04-18得票数 4
回答已采纳
5回答
若F.中G的每个圈至少有一条边，则称边的F⊆E集为⊆反馈边集。(b)设G是一个具有正边权的加权无向图。设计了一种有效的求最小权反馈边缘集的算法.
( a) 最小大小反馈边集：，由于图是不加权的，我们可以使用DFS。我们像往常一样从任何顶点开始DFS。( b) 最小权反馈边集：由于图是加权的</e
浏览 6提问于2012-05-29得票数 15
我们必须在一个图中找到从源到宿的路线，在这个图中，最大成本边和最小成本边之间的差值最小。
我尝试使用递归解决方案，但它在循环和修改的dijkstra条件下将失败，这也失败了。
浏览 0提问于2013-04-02得票数 0
3回答
对等价类的元素进行分组的数据结构
、、、、
我必须实现一个对等价类的元素进行分组的数据结构。EquivalenceClass<T>> equivalenceClasses(); Set<T> members();例如，分组的行为如下应该对它进行优化，以填充它并一次获得等价类。
浏览 1提问于2010-12-10得票数 4
回答已采纳
2回答
如果我们修改最短路径问题，使得两个顶点之间的路径的成本是其上边的成本的最大值，那么对于任何一对顶点u和v，它们之间遵循最小成本生成树的路径是最小成本路径。
我如何证明这种方法是正确的？这是有道理的，但我不确定。有没有人知道文献中是否存在这种算法？它有名字吗？
浏览 0提问于2011-11-02得票数 3
回答已采纳
云服务器
ICP备案
云直播
对象存储
实时音视频
腾讯云开发者
