Suppose that G is a directed graph. It was discussed that an algorithm will dete

Question

Suppose that G is a directed graph. It was discussed that an algorithm will determine whether a given vertex can reach every other vertex in the graph (this is the 1-to-many reachability problem). Consider the following similar problem: given graph G, is there any node in G that can reach every other node in G? Such a node is called a “source node”. We want to know whether any node of G is a source node. A trivial algorithm for this is to execute DFS n times, using each node in G as the start node of the DFS. But the total time for this algorithm is O( n* (n+m)).

Describe a linear time algorithm for this “does di-graph G have a source node problem”.

Explanation / Answer

You can do that by running Tarjan's strongly connected components algorithm for finding the strongly connected components in linear time. i.e O(V+E).

The algorithm takes a directed graph as input, and produces a partition of the graph's vertices into the graph's strongly connected components. Each vertex of the graph appears in exactly one of the strongly connected components. Any vertex that is not on a directed cycle forms a strongly connected component all by itself: for example, a vertex whose in-degree or out-degree is 0, or any vertex of an acyclic graph.

Now after finding the strongly connected components, if there is more than one component with no incoming edges, then there can be no node that can reach everywhere i.e. no source node in the graph.

On the other hand, if there is exactly one component with no incoming edges, each node in that component (and no other nodes) can reach everywhere in the graph.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.