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

Question

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

你有什么建议或提示来实现这一点吗？

如果我为每个顶点重复DFS-Visit，则只有第一次顶点是白色的，随后的调用将不起作用。如果在此之前重置颜色，则算法将为O（|V|^2 + |V||E|）。

非常感谢您的帮助！

- Stratford

---

我猜“any to vertex”应该是“任意两个顶点”？ - user529758

你正在寻找最短路径吗？还是所有非循环路径的集合？ - Michelle

Answer 1

将问题分解成子问题，其中您可以使用算法来实现所需的复杂度，如下所示：

• 在结构图上（基础无向图）上使用深度优先搜索（DFS），并找到其中所有的连通分量。将它们称为（V1，E1），（V2，E2），....，（Vk，Ek）
• 对于每个这样的组件，运行您的算法。显然，在不同组件中的两个节点之间没有桥。

复杂度将是：
第一步是 O（V + E）- DFS。
第二步:

• We use the algorithm you developed repeated from each node as black box on each component, so on component i the complexity is O(V_i^2 + V_i*E_i)
• Since in each component i: E_i >= V_i -1 (otherwise it was not connected, a tree has |V|-1 edges), O(ViEi + Vi^2) = O(ViEi).
• Thus, the complexity of this step is O(V1E1 + V2E2 + ... + VkEk).

• Note that for each i E_i <= E, and thus the complexity is not worse then:

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

因此，总复杂度为O(VE)，符合要求。

- amit