Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
By running BFS you will get $O(n.(n+|E|))$ algorithm, and is not bad (except you want faster algorithm). –  Saeed Jan 15 '12 at 13:31
    
@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? –  tamakisnen Jan 15 '12 at 14:26
    
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|))$. –  Saeed Jan 15 '12 at 14:30
add comment

2 Answers 2

up vote 1 down vote accepted

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).

share|improve this answer
    
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). –  Saeed Jan 15 '12 at 16:59
    
@Saeed: There are always strongly connected components. It is possible that some or all components contain only a single node each, however. –  Henning Makholm Jan 15 '12 at 17:23
    
Cool. That's a big improvement. –  tamakisnen Jan 15 '12 at 18:05
    
I fixed the title, for some reason I wrote the opposite thing. –  tamakisnen Jan 15 '12 at 19:00
    
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. –  Saeed Jan 15 '12 at 19:59
show 6 more comments

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.

share|improve this answer
    
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. –  tamakisnen Jan 15 '12 at 11:28
    
Sorry I meant start breadth first search and not horizontal investigation. –  tamakisnen Jan 15 '12 at 12:04
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.