CODEWITHSUNDEEP
algorithmgraphgraph-algorithm
Jake Browning
Jake Browning

Reputation: 218

Find all vertices reachable from a vertex of a directed graph in time O(|E| + |V|)

Where |E| denotes the number of edges, |V| the number of vertices.

My idea is to use depth-first search on the given vertex to find all vertices reachable from it. However as far as my understanding goes, performing depth-first search from only one vertex requires O(1 + out-degree(u)) time, where u is the vertex in question.

Assuming that depth-first search is the answer, why would I have to perform a full O(|V| + |E|) search?

Upvotes: 0

Views: 2102

Answers (2)

Javier Cano
Javier Cano

Reputation: 621

If you perform only one step of the DFS then it is O(1 + outdegree(v)), nevertheless, that will only get you the vertices that are reachable from v at one step, but not all the vertices that you may reach.

Think of the recursion, in order to retrieve all reachable vertices you should perform another recursive DFS search for each reached vertex. In the worst case you will reach all vertices and thus you will have the sum of O(1+outdegree(v)) for each vertex, so you will traverse all the edges of the graph and get O(|V|+|E|).

Upvotes: 2

Juan Lopes
Juan Lopes

Reputation: 10595

Because

(1) you must perform a depth-first search not only in the initial vertex, but also in all vertices that are directly connected to it, and in all vertices those vertices are connected to, and so on.

(2) in the worst case, all the vertices will be reachable from the initial one, and it will be equivalent to perform a full DFS.

Upvotes: 1

Related Questions