Reference no: EM131576872

Question: In this exercise we will develop an algorithm to find the strong components of a directed graph G = (V , E). Recall that a vertex w ∈ V is reachable from a vertex v ∈ V if there is a directed path from v to w.

a) Explain how to use breadth-first search in the directed graph G to find all the vertices reachable from a vertex v ∈ G.

b) Explain how to use breadth-first search in Gconv to find all the vertices from which a vertex v ∈ G is reachable. (Recall that Gconv is the directed graph obtained from G by reversing the direction of all its edges.)

c) Explain how to use parts (a) and (b) to construct an algorithm that finds the strong components of a directed graph G, and explain why your algorithm is correct.