问题标签 [kruskals-algorithm]

令 G = (V, E) 为加权、连通且无向图。让 T1 和 T2 是 2 个不同的 MST。假设我们可以写 E = (A1 UBU A2) 使得：
B 是 T1 和 T2 的边的交点，并且
A1 = T1 - B
A2 = T2 - B

假设 G 中的每一个 MST T 都包含 B 的所有边，找到一个算法来判断是否存在一个 MST T 包含 A1 中的至少一条边和 A2 中的至少一条边。

编辑：我已经放弃了这里的部分。我认为它弊大于利。

我制作了以下节点和弧结构：

现在我想制作一个图形数据结构，以便能够在其上实现 Kruskal 算法。我无法理解如何利用这两个结构。每个节点都存储其名称和坐标以及有关往返于它的弧的信息。所以我有一个节点集群，但我如何将所有东西链接在一起。这里没有根节点。我应该在我的图表类中添加什么？我已经搜索了邻接列表和矩阵，但不明白如何将我的想法与它们联系起来？请解释

我如何使用 Kruskal 算法计算 im R(3.0.0 - Linux x32) 最小生成树？

我使用 igraph (0.6.5) 库创建了一个加权完整图，如下所示：

而且我能够用 Prim (igraph) 计算最小生成树

但不幸的是没有在“igraph”克鲁斯卡尔的算法中实现。

我可以将我的生成图表示为 data.frame：

有没有一种简单的方法可以用 R 中的克鲁斯卡尔算法计算 mst？

我正在完成斯坦福 CS106B C++ 课程的作业，但我在很大程度上坚持实施 Kruskal 的算法来找到最小生成树。

更具体地说，我无法弄清楚确定是否将弧/顶点添加到树的逻辑。这些是我得到的指示：

“您将使用的策略基于跟踪连接集。对于每个节点，维护与其连接的节点集。在开始时，每个节点仅连接到自身。添加新弧时，您合并两个端点的集合成一个更大的组合集合，两个节点现在都连接到。考虑弧时，如果它的两个端点已经属于同一个连接集，则添加该弧没有意义，因此您跳过它。 "

我知道这条线：

需要改变。有谁知道它应该是什么？:)

我希望找到图 G 的最小生成树，使其包含边 e，并且它的权重是所有具有边 e 的生成树中的最小值。如果我包含边 e，然后运行 ​​prime 或 kruskals，它会工作吗？

假设图 G 中的边权重均匀分布在 [0,1) 上。哪种算法 prims 或 Kruskals 会更快？我认为这将是 kruskals，因为我们可以利用特定的排序算法，因为排序是 kruskals 算法的瓶颈步骤。

我编写了将顶点添加到图中的代码并更新边的权重，然后找到最小生成树。我认为我已经做到了，但似乎有一些错误，但我找不到它。使用 Valgrind 的系统并在 MST 的调用中指示“大小为 4 的无效写入”和“大小为 4 的无效读取” ，但我认为它工作正常。Valgrind 的整个错误是https://docs.google.com/document/d/1_AhOdDkyZGNTBVHspyGtnSQoU1tYkm0nVA5UABmKljI/edit?usp=sharing

下面的代码被like调用

结果将是 (1,2) (2,4) (3,4)。

并打电话

结果将是 (1,2) (1,3) (2,4)。

它被发送到系统执行，它将像上面一样被调用，但在上面的很多时间周期中。

我有一个ArrayList<Edge>我必须删除重复值的地方。 Edge类如下

我想计算一个图的最小生成树来实现Krushkal 算法。为了计算，我必须Edge从列表中删除所有重复的 s。那么哪种算法最适合从这种具有 srcNode、destNode 和 edgeWeight 的数据结构中删除重复值。

我已经计算了一个 MST，现在我正在尝试通过向图中添加一个新节点 v 并将事件边添加到 G 来更新它。我的想法是我们需要从新边到最近的顶点计算一个新的 MST'现有的 MST 并应用 Kruskal 算法连接这 2 个 MST。虽然我不确定这是否是正确的选择以及该算法的运行时间是多少。

我正在尝试实现 Kruskal 算法，并在 MST 中找到权重之和。我认为我的问题出在我设置每个节点的父节点的地方，但我不确定，因为在小例子中它工作正常，但是在大例子中它没有检测到循环，最终答案是错误的。所以我的发现可能是错误的，但我不确定。这是我的代码：