0
$\begingroup$

What happens if you run Kosaraju’s algorithm for finding strongly connected components of directed graphs on a DAG?

$\endgroup$
  • 2
    $\begingroup$ What do you think of it? What is your specific question? $\endgroup$ – hengxin May 29 '17 at 7:54
  • 3
    $\begingroup$ Try it and see what happens! $\endgroup$ – Yuval Filmus May 29 '17 at 10:30
3
$\begingroup$

We should think about the property of SCC(strongly connected component)

A directed graph $G(V, E)$ is acyclic if and only if $G$ has no SCCs with more that one vertex. Because a directed cycle is SCC by definition of the cycle.

Hence, the result of the Kosaraju’s algorithm on a DAG will return $|V|$ trivial SCCs. In other words, it returns $\{\{v\}\mid v\in V\}$.

| cite | improve this answer | |
$\endgroup$

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.