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?
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
answered Oct 10, 2022 at 14:02