Proving an algorithm for decomposing a digraph into SCC’s is correct
Use Kosaraju’s
Definition of Kosaraju’s for a graph G:
- Run DFS on , the reverse graph of G, saving post-orders
- Run DFS on G considering nodes in decreasing post order (sink to source)
What Kosaraju’s essentially does
- DFS highest post order usually finds source vertex but need sink, so we DFS traverse reverse graph (verify reverse graph gives source) isntead
- runs dfs on G