作为无向无权图输入的两个任意顶点之间的最小割
我有一个无向加权图，我需要找到分隔两组顶点的最小切口。我可以修改我的设置，以便将问题减少到找到分隔两个给定顶点的最小切口。我想补充的是，权重是正数和分数。
Stoer–Wagner算法除了将指定的节点保留在切割的不同侧面之外，什么都可以做，我很好奇是否有办法修改SW来做到这一点。
非常感谢。
共有1个答案
关于斯托尔·瓦格纳还不确定，但解决这个问题的另一个典型方法是使用MaxFlow。
将一组节点链接到源，另一组链接到具有无限容量的目标。每隔一条边的权重应为1，然后在生成的图形中执行MaxFlow。
完成后，标记剩余网络中仍可从源访问的所有节点（上次路径查找运行中访问的节点）。在原始图中，位于标记节点和未标记节点之间的任何边都是最小割的一部分。
-
我有一个算法来寻找有向图从一个顶点u到任何其他顶点的边，它具有O(V+E)的时间复杂度（基于DFS）。我必须开发一个算法来找到O(VE)中任意两个顶点u和v之间的边。 你有什么建议或暗示来实现这一点吗？ 如果我对每个顶点重复dfs-visite，那么只有第一次顶点是白色的，接下来的调用将不起作用。如果我在做之前重置颜色，那么算法将是O(v^2+VE)。 提前谢谢你！
-
在无向赋权图中寻找两个顶点之间的最短路径。还已知权重是小于log（logV）的整数，其中V是顶点的数量。使用贝尔曼-福特或Dijkstra算法很容易解决，但是有没有什么算法可以更快地解决呢？ 到目前为止，我一直在考虑使用BFS，将权重大于1的边划分成两个权重为1的边，但如果V是大数，就不是一个好主意。不，这不是我的家庭作业，我只是在想。
-
枚举任意图中两个顶点之间的所有简单路径通常需要指数时间，因为顶点之间可能存在指数数量的简单路径。但是如果我们只对两个endpoint顶点之间至少一条简单路径上的顶点感兴趣呢？ 也就是说：给定一个无向图和两个不同的顶点，是否有多项式时间算法可以找到两个顶点之间至少一条简单路径上的每个顶点？这与连通性不同；不包括死胡同和死胡同。然而，分支和连接路径是允许的。 我发现编写一个看起来可以解决这个问题的算法
-
我需要帮助在一个未加权无向图中找到两个节点之间的所有最短路径。 我能够使用BFS找到一条最短路径，但到目前为止，我还不知道如何找到并打印出所有路径。 知道我可以使用的算法/伪代码吗？
-
给定一个加权无向图和一组节点。 给定两个节点和。 我想找到从到的两条单独的（不重叠的）路径，使两条路径的权重之和最小。我将这个问题解释为标题所描述的，即包含和的最小加权循环。 显然，从到找到第一条最小加权路径然后从图中去掉p1中的边，然后找到第二条最小加权路径是不正确的。 我怎么才能找到这样的循环呢？
-
我试图在Python中提出一种贪婪的算法，该算法在给定某个起始顶点的情况下返回无向图中的顶点。我知道DFS确定是否存在循环，但我正在尝试实际返回形成循环的顶点。我使用邻接矩阵来表示下图： 从图学上讲，这是一个由单个循环组成的无向图。 我当前的思想过程是将起始索引设置为我遇到的第一个＜code＞1）。然后我会查看行的其余部分，看看是否有另一个＜code＞1＜/code＞存在，因为这意味着我的当前顶点