问题标签 [kruskals-algorithm]

我将实现 Kruskal 的算法，我想知道有没有办法用权重绘制形状？我希望用户以某种方式用数字绘制下面的形状，这样我就可以完成其余的工作。

那可能吗？如果是怎么办？我需要一些想法。

我编写了以下代码作为 UVA OnlineJudge 问题 #10034 的解决方案：

它适用于问题提供的测试用例和我在这里找到的更大的测试用例：http: //online-judge.uva.es/board/viewtopic.php?p= 21939#p21939

但是，当我将其提交给 UVA 时，我收到了错误的答案信息。我对 Krukal 算法的实现是否正确？我究竟做错了什么？

网格使用存储在两个数组中的边缘定义图像：

• h[x][y]x,y给出从to的边权重x+1,y
• v[x][y]x,y给出从to的边权重x,y+1

我正在尝试实现 Kruskal 的算法。这相当简单——我可以在网上找到实现并复制它们。问题是处理边缘。具体来说; 对它们进行排序令人困惑。

有没有更好的方法来专门存储这个拍摄的边缘？我希望它们从每个像素到相邻像素。我将图像存储为 i[x][y]，边缘权重只是图像值之间的差异。

我能够为某些输入运行此代码。但在某些情况下，我得到了错误的生成树。例如：如果我在执行程序时输入如下：

输入顶点数：5 输入边数：8

请帮我纠正我的错误...请告诉我我在代码中所做的更改..请

代码如下：

我想在 OpenCL 中实现不相交集数据结构和 Kruskal 算法。我在 OpenCL 中实现了一些代码，但不知道如何开始使用 OpenCL 中的数据结构。Aftab Munshi 书中给出的 Djkstra 算法很难理解。任何人都可以建议其他来源...？

我正在尝试使用不相交集编写 Kruskal 算法的实现。我想我几乎可以正常工作，但我似乎无法让一段代码正常工作。代码需要检查图表上的节点是否已经在它试图添加到的集合中；否则，您不想添加它。这是我正在使用的代码：

一点信息：这个方法是确定两个节点是否已经在同一个集合中。节点数组包含图上的所有点（节点是一个只存储 x 和 y 值并可以检索它们的类。集合是节点的 ArrayLists 数组。在问题开始时，每个节点都将在一个 ArrayList 本身；到最后，它们应该都在同一个 ArrayList 中。索引 1 和 2 对应于 Nodes 数组中的节点。

不幸的是，这段代码似乎没有给我正确的输出；我已经盯着它看了一个多小时，我无法弄清楚问题是什么，所以我希望这里有人能帮助我。

提前致谢。

令 G = (V, E) 为加权、连通且无向图。令 T 为在 Kruskal 算法中增长并在 k 次迭代后停止的边集（因此 T 可能包含少于 |E|-1 条边）。令 W(T) 为该集合的加权和。令 T' 是一个无环边集，使得 |T| = |T'|。证明 W(T) <= W(T')

我理解算法的原始证明，我尝试了几种方法来解决这个问题，但都没有奏效。

例如：我想对 |T| 进行归纳。可能会奏效。对于 |T| = 1 很明显。

我们假设 |T|=k 的正确性并证明（或不……）k+1。通过矛盾假设存在一个边集 T' 使得 |T'|=k+1 并且 W(T') < W(T)。

设 e 为 Kruskal 算法添加的最后一条边。因此，对于 T' 中的任何边 f，W(f) < W(e)（否则我们从 2 个集合中删除边并得到矛盾）。

只有当 T' 中的每条边都已经在 T 中或与 T - {e} 形成一个循环时，才会发生这种情况。

…</p>

注意：这与 Kruskal 算法中的证明不同。我们甚至不知道 T' 是否连通。

我不知道下一步该做什么。我真的很感激任何帮助，在此先感谢

令 G = (V, E) 为加权、连通且无向图，令 T 为最小生成树。令 e 为不在 E 中的任何边（并且具有权重 W(e)）。证明或反证：TU {e} 是一个边集，包含 G' = (V, EU {e}) 的最小生成树。

好吧，这对我来说听起来很真实，所以我决定证明这一点，但我每次都卡住了......

例如，如果 e 是具有最小权重的新边，谁能向我们保证 T 中的边没有以错误的方式选择，这会阻止我们在没有 E 中其他边的“帮助”的情况下获得新的最小权重-T？

我会很感激任何帮助，在此先感谢。

令 G = (V, E) 为加权、连通且无向图，令 e 为 E 中的任意边。展示一个线性时间算法，该算法决定是否存在包含边 e 的最小生成树。

我设法为问题 1 找到了一个奇怪的“解决方案”，它似乎有效，但我认为它不是线性的：

他们建议对每条边 (u,v) 使用 union find 并执行 Union(u,v)，使得 W(u,v) < W(e)。现在，假设 e = (x,y)。现在如果 find(x) != find(y) 那么 x 和 y 没有连接，W(e) 肯定是 Kruskal 算法检查的下一个权重，所以肯定存在一个包含边缘的 MST e.

另一方面，如果 find(x) = find(y) 那么如果我们将 Kruskal 算法运行到这一点，x 和 y 肯定会连接，所以我们不能将边 e 添加到任何 MST（通过操纵具有相同权重的边的排序顺序 - Kruskal 算法可用于创建任何 MST）。

我不明白为什么这是线性的？由于工会，它不应该花费 O( |E| alpha(|V|) ) 吗？

也许还有另一种方法可以在线性时间内做到这一点？

提前致谢

令 G = (V, E) 为加权、连通且无向图。描述一个有效的算法，它决定 G 中是否正好有 2 个不同的 MST。

我已经解决的上一个问题要容易得多：描述一种有效的算法来确定 G 中是否正好有一个 MST。

这就是我解决后一个问题的方法：

我们运行 Kruskal 算法，然后将新 MST 的边缘涂成蓝色，其余边缘涂成红色。

然后我使用了另一种我们见过的简单算法（使用 Kruskal），它在包含最大数量红色边的图形中找到一个 MST——这意味着它是图形 G 中的一个 MST，而不管边的颜色如何，并且每隔一个 MST 不能包含比算法找到的 MST 更多的红色边缘。

现在只有一个 MST，如果算法找到相同的 MST（包含所有蓝色边缘）。

这里的另一个问题似乎要复杂得多。我尝试过使用上述算法，也尝试过使用其他各种技巧，但都没有奏效。

顺便说一句，我听说有一种算法可以计算图中不同 MST 的数量，但这确实是一种矫枉过正——我被要求提供一个简单的算法。

我会很感激任何帮助，谢谢