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
    By running BFS you will get $O(n.(n+|E|))$ algorithm, and is not bad (except you want faster algorithm).2012-01-15
  • 0
    @Saeed Well I know that a possible solution is to run BFS for every node until I find one node that will be root and will output only one BFS "forest"(I don't know how it is called). Can you explain how you calculated the execution time?2012-01-15
  • 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
    May be there isn't any strongly connected component, but there is a node such that there is a path between this node and all other nodes (assume directed star).2012-01-15
  • 0
    @Saeed: There are always strongly connected components. It is possible that some or all components contain only a single node each, however.2012-01-15
  • 0
    Cool. That's a big improvement.2012-01-15
  • 0
    I fixed the title, for some reason I wrote the opposite thing.2012-01-15
  • 0
    No there is no need to have always strongly connected component (in this problem), again assume the star graph, and all edges from star node is outgoing edges, all nodes are reachable from star node, but it's just **connected** not **strongly connected** and Tarjan algorithm works for **strongly connected** components.2012-01-15
  • 0
    @Saeed: Tarjan's algorithm _finds_ the strongly connected components. The _point_ of using it is that the graph you give as input is not necessarily strongly connected. In your case each node would constitute a strongly connected component of its own, which is what Tarjan's algorithm would find.2012-01-15
  • 0
    Yes I see, I didn't read your second paragraph before.2012-01-15
  • 0
    @HenningMakholm I have accepted this answer as correct but it is not answering fully the question. That was ok for me cause I wanted to dig in the algorithm and understand it. I think it will be useful to edit your answer.2012-01-18
  • 0
    @tamakisnen: What do you think is lacking?2012-01-18
  • 0
    @HenningMakholm I don't believe that something is missing cause you actually answered my question but you are focusing on finding a node that is reachable from everywhere(that was my mistake, I fixed the title) and I think that it would be good for future readers to fix that.2012-01-18
  • 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
    One possible solution might be to start a horizontal investigation and then see if the result has one tree and s is a root. Am I a right? The problem is that I cannot prove if this is a good algorithm for this problem and find its execution time.2012-01-15
  • 0
    Sorry I meant start breadth first search and not horizontal investigation.2012-01-15