有没有一种算法在无向图中找到最小割来分离源和汇
我还知道Ford-Fulkerson的无向图最大流算法的一个修改，它用两条相反的有向边替换每个无向边，同时更新流到这两条边。但经过修改后，最大流最小割定理似乎不再有效，因为在下面的无向图上，最小割将无法正确确定：
nodes: 0, 1, 2, 3
edges & capacities: {0,1}->5, {0,2}->6, {1,2}->2, {1,3}->7, {2,3}->4
source: 0
sink: 3
最大流最小割定理说，最小割是那些流等于它们的容量的边，而修正的Ford-Fulkerson则是所有的边，这显然不是正确的割。
我找到了一个Stoer-Wagner算法来寻找无向图的全局最小割，但这不是我想要的，因为这个算法不考虑任何源和宿，而是可以找到一个割，它让节点在同一个组件中。
有没有一个算法，可以有效地在一个无向图中找到一个最小割，它有源和宿，分离这两个指定的节点？我是否可以修改前面提到的算法，使其适用于我的案例？
共有1个答案
您可以使用Ford-Fulkerson算法的一些修改。
- 首先需要找到源和汇之间的最大流量并记住它。
- 从图形中删除某些边。
- 则需要在新图中找到最大流量。如果最大流量与步骤一不相同，则此边缘在最小切口中。
- 将边返回到图形，选择另一条边，然后转到步骤2。
在求最大流时，只需将无向边看作两个具有相同容量的有向边。
-
问题内容： 在Python解释器中执行了这些指令后，将获得一个带有绘图的窗口： 不幸的是，当程序进行进一步的计算时，我不知道如何继续以交互方式探索创建的图形。 有可能吗？有时计算很长，如果可以在检查中间结果时进行计算，则将有所帮助。 问题答案： 使用不会阻塞的呼叫： 使用： 使用交互模式：
-
这是我的算法。 我做了一个。每次当我找到时，我都知道我得到了一个有向循环。 然后我将暂时沿着向后（直到我在循环中遍历所有顶点），并计算。 我的算法正确吗？ 如果我的算法正确，时间复杂度是多少？ 这个问题有没有更好的算法？
-
设想一个有向无环图如下所示，其中： “a”是根（总是正好有一个根） 每个节点都知道其父节点 节点名称是任意的-不能从中推断出任何内容 我们从另一个来源了解到，节点是按照A到G的顺序添加到树中的（例如，它们是在版本控制系统中提交的） 我可以使用什么算法来确定两个任意节点的最低共同祖先(LCA)，例如： null 注： 从根到给定节点不一定只有一条路径（例如“g”有两条路径），所以不能简单地遍历从根到
-
问题内容： 在Python解释器中执行以下指令后，将获得一个带有绘图的窗口： 不幸的是，当程序进行进一步的计算时，我不知道如何继续以交互方式探索创建的图形。 有可能吗？有时计算很长，如果可以在检查中间结果时进行计算，则将有所帮助。 问题答案： 使用不会阻塞的呼叫： 使用： 使用交互模式：
-
我需要为一组有向无环图找到从节点 0 开始的最长路径。我正在使用维基百科中的最长路径问题算法。我已经让算法适用于大多数图形，但对于其他图形，它没有给出正确的结果。算法为： 图形实现使用邻接列表来存储图形。如果我传递一个图，例如： 我得到的答案5，这是正确的。但是，如果我通过图表： 然后我得到2，而正确答案应该是3。 我使用的TopSort2算法是： DFS 算法包括：
-
我们已经看到，树的生成和切割是密切相关的。这里有另一个联系。让我们移除Kruskal算法添加到生成树中的最后一条边；这将树分解为两个组件，从而在图中定义一个截（S,S）。我们对这个伤口能说什么呢？假设我们正在处理的图是未加权的，并且它的边是均匀随机排列的，以便Kruskal的算法处理它们。这里有一个值得注意的事实：在概率至少1/n^2的情况下，(S，S)是图中的最小割，其中割的大小(S，S)是S和