1
$\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?

$\endgroup$
3
  • $\begingroup$ What does "walking the edges in reverse fashion" mean? $\endgroup$ Commented Sep 7, 2018 at 7:07
  • $\begingroup$ Traverse the edge $\endgroup$ Commented 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$ Commented Sep 7, 2018 at 9:17

1 Answer 1

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.

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