2
$\begingroup$

If we have a directed graph $G = (V,E)$ and we want to find if there is such node $s \in V$ that we can reach all other nodes of $G$

What is a good algorithm to solve this problem and what is its execution time?

  • 0
    Each BFS Takes $O(n+|E|)$ to run, and because you should run it at most $n$ times, it takes $O(n\times (n+|E|))$.2012-01-15

2 Answers 2

2

Run Tarjan's linear-time algorithm for finding strongly connected components.

If there is more than one component with no incoming edges, then there can be no node that can reach everywhere.

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.

(If you're looking for nodes that are reachable from everywhere -- as in the original the title of the question said -- look instead for components with no outgoing edges).

  • 0
    @tamakisnen: Oh, you changed the title to the dual question. Answer changed to the dual too, then.2012-01-19
3

Perhaps the section about algorithms at the wikipedia article on reachability has what you need. Why not have a look and let us know?

You can also search for "Warshall's algorithm," although this may do more than you need.

  • 0
    Sorry I meant start breadth first search and not horizontal investigation.2012-01-15