0
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\begingroup$ What does "walking the edges in reverse fashion" mean? $\endgroup$
    – Yuval Filmus
    Sep 7, 2018 at 7:07
  • $\begingroup$ Traverse the edge $\endgroup$
    – Radu Stoenescu
    Sep 7, 2018 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, 2018 at 9:17

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

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

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