在时间O（| E | + | V |）中查找从有向图的顶点可到达的所有顶点

Where | E |表示边的数量，| V |顶点的数量。在时间O（| E | + | V |）中查找从有向图的顶点可到达的所有顶点

我的想法是在给定顶点上使用深度优先搜索来查找可达到的所有顶点。然而就我的理解而言，仅从一个顶点执行深度优先搜索需要O（1 + out-degree（u））时间，其中u是所讨论的顶点。

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

来源

2015-04-19 Jake Browning

只有一个顶点的DFS需要O（| E |）。考虑一个完整的图表作为最坏的情况，即DFS将遍历每个边缘，即使是单个顶点也是如此。您应该意识到“所有顶点可达”是指直接或间接通过另一个顶点，即传递。 – stephan

由于

（1）必须不仅在初始顶点，而且在直接连接到它的所有顶点进行深度优先搜索，并在所有的顶点这些顶点被连接到，并等等。（2）在最坏的情况下，所有的顶点都可以从最初的点到达，这相当于执行完整的DFS。

来源

2015-04-19 16:41:16

在我学习的情况下，DFS是使用递归dfsFromVertex（v）函数实现的，该函数声明了时间Ɵ（1 + out-degree（v））。这是否意味着在更坏的情况下Ɵ（1 + out-degree（v））=Ɵ（| V | + | E |）？这部分让我困惑，因为out-degree（v）可以是| V |最多。我在猜测，我错误地认为1（1 + out-degree（v））是整个递归的时间复杂度，但也许它只是递归的一次迭代的运行时间。 –

是，每个顶点的Ɵ（1 + out-degree（v））将总共为Ɵ（| V | + | E |）。一个非常着名的图论理论指出，每个图中所有顶点的所有度的和为2 | E |。是的，这个Ɵ（1 + out-degree（v））用于每个递归步骤，并且每个顶点只有一个递归步骤。 –

如果您只执行DFS的一个步骤，那么它就是O（1 + outdegree（v）），但是，它只会得到在一个步骤中从v到达的顶点，但不是所有的顶点你可能会达到。

想想递归，为了检索所有可到达的顶点，您应该为每个到达的顶点执行另一个递归的DFS搜索。在最坏的情况下，你将到达所有顶点，因此你将得到每个顶点的O（1 + outdegree（v））的总和，所以你将遍历图的所有边并得到O（| V | + | E |）。

来源

2015-04-28 21:37:57

在时间O（| E | + | V |）中查找从有向图的顶点可到达的所有顶点

回答

相关问题