求有向图中任意两个顶点之间的所有边
我有一个算法来寻找有向图从一个顶点u到任何其他顶点的边，它具有O(V+E)的时间复杂度（基于DFS）。我必须开发一个算法来找到O(VE)中任意两个顶点u和v之间的边。
你有什么建议或暗示来实现这一点吗？
如果我对每个顶点重复dfs-visite，那么只有第一次顶点是白色的，接下来的调用将不起作用。如果我在做之前重置颜色，那么算法将是O(v^2+VE)。
提前谢谢你！
共有1个答案
将问题拆分为子问题，在这些子问题中，您可以使用您的算法来实现所需的复杂性，如下所示：
- 在结构图（底层无向图）上使用DFS，找到其中所有连通的分量。设它们是（V1,E1),（V2,E2),....,（Vk,Ek)
- 对于每个这样的组件，运行您的算法。显然，不同组件中的两个节点之间没有桥接。
复杂性将是:
步骤1是O(V+E)-DFS。
步骤2：
O(V1E + V2E + ... + VkE) = O(E *(V1+V2+ ... + Vk)) = O(VE)
-
枚举任意图中两个顶点之间的所有简单路径通常需要指数时间，因为顶点之间可能存在指数数量的简单路径。但是如果我们只对两个endpoint顶点之间至少一条简单路径上的顶点感兴趣呢？ 也就是说：给定一个无向图和两个不同的顶点，是否有多项式时间算法可以找到两个顶点之间至少一条简单路径上的每个顶点？这与连通性不同；不包括死胡同和死胡同。然而，分支和连接路径是允许的。 我发现编写一个看起来可以解决这个问题的算法
-
以下是练习： null null 我的算法正确吗？如果我做v到w，然后做w到v，这仍然被认为是线性时间吗？
-
我有一个无向加权图，我需要找到分隔两组顶点的最小切口。我可以修改我的设置，以便将问题减少到找到分隔两个给定顶点的最小切口。我想补充的是，权重是正数和分数。 Stoer–Wagner算法除了将指定的节点保留在切割的不同侧面之外，什么都可以做，我很好奇是否有办法修改SW来做到这一点。 非常感谢。
-
本文会围绕算法中DFS求有向图或无向图两点间所有路径，先讲解DFS以及有向图或无向图的意思。 有向图在图中的边是有方向的，表现出来就是有个箭头指示方向，节点只能单向通信或传递消息，相当于单行道，无向图边没方向是双向的，边连接的两个节点有通路可以双向通信，类似于双行道。 无向图，边没有方向的图称为无向图。邻接矩阵则是对称的，且只有0和1，因为没有方向的区别后，要么有边，要么没边。 DFS作为搜索算法
-
我有一个有向加权图
-
我有一个有向加权图G，其中权重是过渡的持续时间。 我使用DFS编写了两个顶点之间的所有路径搜索算法，并进行了修改：搜索将继续，直到路径的总权重（其各部分的权重之和）小于某个值。 我的代码在小图中工作，但在大图中（| V |=1800，| E |=50870）它会冻结。