Graph

Question

The problem of finding the set of vertices reachable from a given vertex in a graph can be solved in time

A. O(|V|^2)

B. O(|V| + |E|)

C. O(|V||E|)

D. none of these

Comments

What if adjacency matrix used?in that case it would be O(n^2)

Answer 1

B) O (V+E)

Perform BFS

Comments

Shouldn't it be DFS ?

Question asks for all reachable vertices, not only the adjacent ones.

And please explain "how O(V + E) ?" .

---

BFS  search the graph breadth wise, searching means it picks a source vertex and spans along the width of the graph. Rember it can be used to make a spanning tree
If u use adjacency list representation of graph u get a runtime of O(V+E)