2
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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.
$\endgroup$

Your Answer

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

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