用Kruskal算法求图的最小割？
我们已经看到，树的生成和切割是密切相关的。这里有另一个联系。让我们移除Kruskal算法添加到生成树中的最后一条边；这将树分解为两个组件，从而在图中定义一个截（S,S）。我们对这个伤口能说什么呢？假设我们正在处理的图是未加权的，并且它的边是均匀随机排列的，以便Kruskal的算法处理它们。这里有一个值得注意的事实：在概率至少1/n^2的情况下，(S，S)是图中的最小割，其中割的大小(S，S)是S和S之间交叉的边的个数。这意味着重复该过程O(n^2)次并输出找到的最小割以高概率产生G中的最小割：一个非加权最小割的O(Mn^2logn)算法。进一步的调整给出了David Karger发明的O(n^2logn)最小割算法，它是解决这一重要问题的最快算法。
如果只是遍历每条边并检查边是否是最小切口，不是更容易吗？在n个结点的图中，唯一边的最大个数为n+n-1+n-2...+1条边，小于n^2。考虑到n^2小于n^2对数n，为什么不只是循环所有边，因为这样更快呢？
共有1个答案
我想你可能误解了算法的工作原理。该算法的工作原理是运行Kruskal的算法，直到添加最后一条边，然后在此之前停止。算法不试图建立这些“最后边”的集合；相反，重复运行Kruskal算法的O(N2)随机迭代，以便建立O(N2)可能的割。在所有这些候选割中取最低的割，然后以高概率给出最小割。换句话说，如果边少于O(N2)也没关系。重要的是留在最后的切口，而不是被考虑的最后一条边。
希望这能有所帮助！
-
这里有一个图，我需要用Prim和Kruskal的算法找到G的最小生成树。 我用普里姆的算法找到了最小生成树。这是我的尝试。 我很难用Kruskal的算法找到最小生成树。我看过许多与Kruskal的图算法相关的视频，但最终得到的图与Prim的算法相同。 谁能给我演示一下如何用Kruskal的算法找到图的最小生成树吗？
-
最小生成树的Kruskal算法 描述：有A、B、C、D四个点，每两个点之间的距离（无方向）是(第一个数字是两点之间距离，后面两个字母代表两个点）：(1,’A’,’B’),(5,’A’,’C’),(3,’A’,’D’),(4,’B’,’C’),(2,’B’,’D’),(1,’C’,’D’) 生成边长和最小的树，也就是找出一种连接方法，将各点连接起来，并且各点之间的距离和最小。 思路说明： Krusk
-
本文向大家介绍Kruskal的最小生成树算法，包括了Kruskal的最小生成树算法的使用技巧和注意事项，需要的朋友参考一下 有一个连通图G(V,E)并给出了每个边的权重或成本。Kruskal的算法将使用图形和成本找到最小生成树。 这是合并树方法。最初，有不同的树，此算法将采用成本最小的那些边合并它们，并形成一棵树。 在此问题中，所有边均根据其成本列出并排序。从列表中，取出成本最低的边并添加到树中，
-
问题 用Kruskal算法求无向图 G 的最小生成树。 解法 Kruskal算法是一种贪心算法。初始时将图 G 的边集 E 按照权值，从小到大进行排序，并且生成树。从最小权值的边开始，依次考虑每一条边，对于边 e_i 来说，若将它加入生成树集合 S 中， e_i 不会与 S 中已有的边形成环，那么选取边 e_i 作为生成树中的一条边，将其加入集合 S ；反之若将 e_i 加入 S 中会与已有的边形
-
我需要一些关于Prim的算法问题的帮助： 设T是图G的一个由Prim算法得到的最小生成树。设Gnew是在G上增加一个新的顶点和一些带权的边，将新的顶点连接到G上的一些顶点而得到的图，我们能把其中一条新的边加到T上构造Gnew的最小生成树吗？如果你回答是，请解释是怎样做的；如果没有，请解释原因。 提前谢谢！！
-
本文向大家介绍python最小生成树kruskal与prim算法详解，包括了python最小生成树kruskal与prim算法详解的使用技巧和注意事项，需要的朋友参考一下 kruskal算法基本思路：先对边按权重从小到大排序，先选取权重最小的一条边，如果该边的两个节点均为不同的分量，则加入到最小生成树，否则计算下一条边，直到遍历完所有的边。 prim算法基本思路：所有节点分成两个group，一个为