Search code examples
graph-theorydepth-first-searchstrongly-connected-graph

Strongly Connected Components : Kosaraju algorithm

In Kosaraju algorithm I came across two possible implementations:

1) Search for strongly connected components in the reversed graph in the topological order of vertices in the original graph.

2) Search for strongly connected components in the original graph in the topological order of vertices in the reversed graph.

I wanted to that is it wrong to search for strongly connected components in the original graph using vertices in its reversed topological order. This will be better in terms of memory also as there is no need for a new adjacency list.

sources :1) E-Maxx , 2) CLRS book

Solution

  • Terminology issues:

    You are talking about topological ordering, but topological order exist if and only if the graph is DAG (directed acyclic). In case you want to work only with DAGs then you already have SCC (strongly connected components) as each vertex is component for itself. If you want to find SCC on directed graphs then you need to change topological ordering to DFS finishing times. CLRS book mentions only finishing times f[u]:

    1. Call DFS(G^T), but in the main loop of DFS, consider the vertices in order of decreasing f[u]...

    Reformulation of your question:

    Is it wrong to search for strongly connected components in the original graph consider vertices in order of increasing finishing times f[u]?

    Answer:

    Yes, it is wrong.

    Counterexample: Consider the following graph:

    enter image description here

    which contains two components C and C'. If you run first DFS (starting from the node u) you will end up with one of the two following lists in ascending order by finishing time:

    DFS list 1: {v,w',w,u}

    DFS list 2: {w',v,w,u}

    What you actually ask is whether you can process these lists from the beginning on the original graph. If you choose the first list you will extract component C' via DFS search starting from node v, and then component C via DFS search starting from node w'. But if you choose the second list and start DFS from node w' on original graph you will get only one component (whole graph), which is wrong.

    Note that Kosaraju's algorithm works in both cases, as it starts from the end of a list (node u in both cases) and extract component C via DFS search on reversed graph. Component C' will be extracted later when we reach node v in the list.