So I'm watching Stanford's algorithm lectures and I'm on Kosaraju's algorithm. In the lecture, the algorthm was given in 3 steps: calculate the graph with all arcs reversed, run dfs on reversed graph, run dfs on original graph. Then an optimization was given, which was to instead of using the naive implementation of remaking the entire graph with the arcs reversed, you can instead run dfs on the original graph but going backwards along the arc instead of forward, which simulates running dfs on the reversed graph.

The lecturer made it seems so simple to do this and gave no further explanation. I'm completely stumped on how you can achieve this. Can someone give me some help or point me in the right direction?

You can instead run dfs on the original graph but going backwards along the arc instead of forward, which simulates running dfs on the reversed graph.

This depends entirely on how you're storing your graph. It'd be easy to do if you use and adjacency matrix, but not if you use an adjacency list.

If you use and adjacency matrix $M$ where $M[x, y] = 0$ means no edge between the nodes $x$ and $y$ and $M[x, y] = n$ means an edge from $x$ to $y$ with weight $n$ (use 1 instead of $n$ if you don't have weights along your edges)

Let's say during the DFS on the reverse graph, you're at a node $a$ and you have to look at $a$'s neighbors (along reversed edges). To check if $b$ is a neighbor of $a$, you can simply check if $M[b, a]$ is nonzero.

Just take the code for DFS and, every time it says "If there is an edge from $x$ to $y$", replace that with "If there is an edge from $y$ to $x$."

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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