问题标签 [kargers-algorithm]

我正在实施 Karger 的算法。据我了解，最后两个节点之间的边数并不总是最小切。我难以理解的是我如何真正从这个算法中得到最小切分。我一直在寻找很多关于概率的东西，但对我来说这一切都像是胡言乱语......

根据我的阅读，我认为我需要在图表上多次运行 Karger 算法。这将使我很有可能成功击中最小切线。我认为？...

有人可以用更简单的方式解释一下吗？如何找到运行此算法的次数？我上面所说的是否正确？

在 python 中实现 Karger 的最小切割算法时，我得到的输出为

这是否意味着最小削减是5？我正在使用以下代码：

我正在尝试在 python 中学习 Karger 算法，但我不确定这是否正确。

我试图编写一个 Karger 算法的实现来解决最小切割问题。这是我的代码

它没有评论，但它应该是不言自明的。'g' 是一个字典，其键是图的顶点，每个顶点的值都是它所连接的顶点。randomVertices 为我提供了我想要收缩的边缘，而 mergeVertices 通过删除第二个顶点、更新链接到该顶点的键的值以及摆脱自循环来更新字典（以及因此的图形）。对我来说它看起来不错，但如果我在任何测试图上运行它，我会在l = g[x]舞台上得到一个 KeyError，我不明白为什么会发生这种情况。希望你们中的一些人可以帮助我。谢谢。

编辑：我的代码实际上很好，错误在于我使用相邻列表加载文件的方式。Cobarzan，谢谢你指出我实际上并没有统一挑选边缘。

我正在尝试在 Java 中实现 min-cut Karger 算法。为此，我创建了一个 Graph 类，它存储一个 SortedMap，一个整数索引作为键，一个顶点对象作为值，以及一个边缘对象的 ArrayList。Edges 存储其事件顶点的索引。然后我合并一些随机边的顶点，直到顶点数达到 2。我重复这个步骤安全的次数。奇怪的是，在我的输出中，我得到了 2 倍的交叉边数。我的意思是，如果正确答案是 10，在执行 n 次算法后（对于 n 足够大），这些执行结果的最小值是 20，这让我相信实现几乎是正确的。这是代码的相关部分：

我正在尝试实现Karger 算法来查找图形的最小切割。关键部分是contract执行单次收缩的方法。到目前为止，这是我的实现（带有“测试”）：

我的问题是，在一次特定的运行中（您可能需要运行几次才能重现此结果），获取邻接列表

其中节点 1 有一个“自循环”——也就是说，它出现在自己的邻接列表中。我不明白这怎么会发生。每次调用都以似乎有效contract的调用结束。remove_self_loops谁能发现这段代码中的错误？

假设给定一个无向、无权图 G= (V, E) 和一些成本函数 c:E→R>0，为每条边 e∈E 分配一个正成本 c(e)。目标是计算最小成本的 G 的最小割（即，由最少边数组成的割中的最小成本割）。给出一个算法，它很有可能在多项式时间内找到这样一个最小成本最小割。你的算法的运行时间是多少？提示：Karger 算法

方法 I：做 Karger n^c 次（仍然是多项式，在 c 的 n 上提高指数）并比较得到的最小切割。c >=1

方法二：当 Karger 处于收缩边缘时，提高高权重的概率。不影响运行时间

甚至两者兼而有之？

我很难理解 Karger 算法如何在无向图上工作的逻辑。我知道有最大流算法，例如 Ford-Fulkersson 算法，但我不是在无向图上使用此算法之后。

有人可以解释在有向图上使用 Karger 算法与在无向图上使用 Karger 算法的区别。

提前致谢！

我试图以与此处解释的相同方式实现 Karger 的最小切割算法，但我不喜欢这样一个事实，即在 while 循环的每一步，我们都可以选择一个边缘，它的两个端点已经在一个超级节点中。更具体地说，这部分

是否有避免此问题的快速解决方案？

在用于无向（可能加权）多重图的Karger 最小割算法中，主要操作是收缩随机选择的边并将其事件顶点合并到一个元顶点中。重复这个过程，直到剩下两个顶点。这些顶点对应于一个切割。该算法可以使用邻接列表来实现。

问题：

1. 我怎样才能找到已选择收缩的特定边缘？

2. 边缘如何收缩（在未加权和/或加权图中）？

3. 为什么这个过程需要二次时间？

编辑：我发现一些信息表明运行时间可以是二次的，因为我们有 O(n-2) 个顶点收缩并且每次收缩可能需要 O(n) 时间。如果有人能解释一下，为什么收缩在邻接列表中需要线性时间，那就太好了。注意收缩包括：删除一个相邻边，将两个顶点合并为一个超节点，并确保剩余的相邻边连接到超节点。

伪代码：

我已阅读相关主题Karger Min cut algorithm running time，但对我没有帮助。另外我没有太多经验，因此非常感谢“外行”术语解释！

我正在尝试实施 Krager 的 Min。python中的cut算法解决以下问题。这个问题来自斯坦福的 edx 课程，“算法：设计与分析，第 1 部分”

该文件包含一个简单无向图的邻接表表示。有 200 个顶点标记为 1 到 200。文件中的第一列表示顶点标签，特定行（除第一列之外的其他条目）告诉所有与该顶点相邻的顶点。例如，第 6 行看起来像：“6 155 56 52 120 ......”。这只是意味着标签为 6 的顶点与标签为 155、56、52、120、......等的顶点相邻（即共享一条边）

运行最小割问题的随机收缩算法，并在上图中使用它来计算最小割。

它涉及以下邻接列表：https ://pastebin.pl/view/39b087f8

这是我在 python 中编写的代码——我知道实现很幼稚，但我只想在优化之前把它弄好。

根据一些互联网搜索，答案似乎是 17。我得到的答案是 20，而且我不认为我的算法实现是正确的，因为解决方案集太多样化了。我相信如果实施得当，解决方案应该经常出现在这个集合中。