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!

$\endgroup$
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.

$\endgroup$
  • $\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$ – Cauthon Dec 31 '14 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$ – Tom van der Zanden Jan 1 '15 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$ – Cauthon Jan 1 '15 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$ – Tom van der Zanden Jan 1 '15 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$ – Cauthon Jan 1 '15 at 11:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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