4
$\begingroup$

$G=<V,E>$ is a directed graph. I need to write an efficient algorithm that finds a $v \in V$ such that there exists a path $\forall w \in V$ $v \rightarrow w$ ($v$ has a path to every other vertex), or "false" if there aren't any. If there are more than one, return one of them.

The obvious and inefficient way would be to run BFS from every vertex, checking after every run of BFS if there are vertices with distance $= \infty$. If not - that vertex has paths to every other vertex. Complexity would be $O(|E||V| + |V|^{2})$.

I can't think of any substantial improvements. If someone could point me in the right direction (pun intended), that would be great!

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
4
$\begingroup$

You'll need to split the graph in to its strongly connected components, and then find a component from which you can reach every other component.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Won't that still leave me with $O(|E||V| + |V|^{2})$? Since we don't know how many SCCs there are, they might be in the same order of the number of vertices (if they're very small SCCs). So wouldn't I still have to run a (modified) BFS from every SCC (the same as doing it from every vertex)? $\endgroup$ Commented Dec 31, 2014 at 23:45
  • $\begingroup$ It is very easy to see for a given connected component which other connected components you can reach from it. $\endgroup$ Commented Jan 1, 2015 at 0:16
  • $\begingroup$ I don't see how to do it under linear time for each and every component. Let's say there are $|V|/3$ strongly connected components. I can start from one of them, and continue to the next, but if every component has only one edge to the next component, I would have to traverse $|V|/3$, doing this for every component. Obviously if it's that easy I'm missing something simple... $\endgroup$ Commented Jan 1, 2015 at 10:34
  • $\begingroup$ Does the graph made up by the strongly connected components (treating every component as a vertex) have any special properties? Can you find some (logical) ordering for the components? $\endgroup$ Commented Jan 1, 2015 at 10:46
  • $\begingroup$ Right, it must be a DAG, so if we sort it topologically, we must check only the first SCC, correct? Thanks! $\endgroup$ Commented Jan 1, 2015 at 11:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.