algorithm - 在时间 O(|E| + |V|) 内找到从有向图的一个顶点可达的所有顶点

Question

在哪里|E|表示边的数量，|V|顶点数。

我的想法是在给定的顶点上使用深度优先搜索来找到从它可以到达的所有顶点。然而，据我所知，仅从一个顶点执行深度优先搜索需要 O(1 + out-degree(u)) 时间，其中 u 是所讨论的顶点。

假设深度优先搜索是答案，为什么我必须执行完整的 O(|V| + |E|) 搜索？

Answer 1

如果您只执行 DFS 的一步，那么它是 O(1 + outdegree(v))，但是，这只会让您在一步中获得从 v 可到达的顶点，而不是您可以到达的所有顶点可能达到。

考虑递归，为了检索所有可到达的顶点，您应该对每个已到达的顶点执行另一个递归 DFS 搜索。在最坏的情况下，您将到达所有顶点，因此您将获得每个顶点的 O(1+outdegree(v)) 之和，因此您将遍历图形的所有边并获得 O(|V|+|E |).