0
$\begingroup$

I am studying graph algorithms, and I know that in algorithm theory there has to be an invariant of sorts that stays the same during the algorithm run that makes the algorithm valid and right to use. But I can't seem to find the invariant in Kosaraju's algorithm for finding strongly connected components. What is it that stays the same when we traverse the inverted graph in order produced by DFS-traversing the original one?

$\endgroup$

1 Answer 1

2
$\begingroup$

I think that there are several invariant, but the one that seems most important is the following:

« for any edge $(u, v)\in E$, if the SCC of $u$ has been visited, then the SCC of $v$ has been visited »

That means that you are visiting SCC's from sinks to sources.

$\endgroup$

Your Answer

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

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