I was watching a lecture on determining the strongly connected components of a graph using Kosaraju's algorithm and the lecturer claimed one can easily walk the edges in reverse fashion.

While I see this happening with an adjacency matrix representation(the reverse is the matrix transpose, and you can determine its elements on demand), I'm having a hard time coming up with a solution in the case of the adjacency list representation.

Any hints?

  • $\begingroup$ What does "walking the edges in reverse fashion" mean? $\endgroup$ – Yuval Filmus Sep 7 '18 at 7:07
  • $\begingroup$ Traverse the edge $\endgroup$ – Radu Stoenescu Sep 7 '18 at 7:28
  • 1
    $\begingroup$ you can create a new adjacency list representing the reverse of all edges in O(e) time. Trivially $\endgroup$ – ratchet freak Sep 7 '18 at 9:17

You can iterate over all of the edges in $O(|E|)$ time. So, construct a copy of the graph with reversed edges as follows: iterate over all the edges, and as you examine each edge, add the reversed edge to the copy. That takes $O(|E|)$ time in total, and you only need to do it once, as a pre-processing step. Now, during Kosaraju's algorithm, if you ever need to walk edges in a reversed fashion, you can just refer to the reversed graph you created earlier.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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