algorithm - 在有向图中找到任意两个顶点之间的所有边

Question

我有一种算法可以找到从顶点u到具有 O(|V|+|E|) 时间复杂度（基于 DFS）的任何其他顶点的有向图的边。我必须开发一种算法来找到O(|V||E|) 中任意两个顶点u和v之间的边。

您有任何建议或提示来实现这一目标吗？

如果我对每个顶点重复 DFS-Visit，只有第一次顶点是白色的，接下来的调用将什么也不做。如果我在此之前重置颜色，那么算法将是 O(|V|^2 + |V||E|)。

提前非常感谢您！

Answer 1

将问题拆分为子问题，您可以在其中使用算法来实现所需的复杂性，如下所示：

• 在结构图（底层无向图）上使用 DFS，并找到其中的所有连通分量。让他们成为 (V1,E1), (V2,E2), ...., (Vk,Ek)
• 对于每个这样的组件，运行你的算法。很明显，在不同组件中的 2 个节点之间没有桥梁。

复杂性将是：
第 1 步是O(V+E)- DFS。
第 2 步：

• 我们使用您从每个节点重复开发的算法作为每个组件上的黑盒，因此组件i的复杂性是O(V_i^2 + V_i*E_i)
• 因为在每个组件中i：（E_i >= V_i -1否则它没有连接，一棵树有|V|-1边）O(ViEi + Vi^2) = O(ViEi)，.
• 因此，这一步的复杂度为O(V1E1 + V2E2 + ... + VkEk)。

• 请注意，对于每个i E_i <= E，因此复杂性并不差：

  O(V1E + V2E + ... + VkE)  = O(E *(V1+V2+ ... + Vk)) = O(VE)
  

因此，根据需要，总复杂度为O(VE)。