For kosaraju's algorithm to traverse the graph in reverse order the naive solution is to reconstruct the original input graph in reverse order and dfs on it. Is there any way I can avoid creating copy of the graph in reverse order? how can I dfs on the same original graph going back across the edges?
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
The only solution I came up with is at the expense of the algorithm's neat linear complexity.
This could still be useful if you need to save up on resources at the expense of running time.
The idea is:
- At every time you land on a new node A, you go through all of the "not-visited" nodes.
- For each node you check if there is an edge that goes from that node B to the current node A.
- If there is such edge B -> A, then DFS(B) using this same approach.
