How to traverse a graph in reverse with dfs

Question

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?

David Richerby · Answer

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$."

Peeyush Kushwaha · Answer

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.

Let's say you use an 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.

How to traverse a graph in reverse with dfs

2 Answers

Add your own answers!

Ask a Question