CODEWITHSUNDEEP
algorithmgraphdepth-first-searchstrongly-connected-graphkosaraju-algorithm
tingting
tingting

Reputation: 11

Can the finishing times for Kosaraju's algorithm be generated from the original graph, not the reverse graph?

In Kosaraju's algorithm, finishing times are generated from the reversed graph. Then, the strongly connected components are discovered from the original graph by performing DFS, starting from the greatest to the lowest finishing times generated earlier.

Can the finishing times for Kosaraju's algorithm be generated from the original graph? Then, could the strongly connected components be discovered by performing DFS, starting from the lowest finishing time to the greatest finishing time?

It seems to me like it would be the case, but that's just my hunch.

Upvotes: 1

Views: 565

Answers (2)

RomanGirin
RomanGirin

Reputation: 75

Kosaraju algorithm in short is:

  1. reverse graph;
  2. take reversed post order of DFS on the reversed graph;
  3. DFS through original graph using the order you get on the step 2 (not visiting the same node twice of course).

So if step 1 is skipped the non-working-example can be simplified to two node graph: A <-- B.

Skip the 1st step. Start from B, reversed post order is: B, A, so DFS on the original graph using the order gives one SCC, which is wrong.

At the same time using the same graph A <-- B, the complete correct algorithm (even if started from the 'inconvenient' node B):

  1. reverse: A --> B;
  2. reversed post order A, B;
  3. DFS on the origin graph using the order gives two SCCs (which is correct).

Of course the same result (two SCCs) you get if start the algorithm's 1st step from the A node. It works as you get the same order on the 2nd step: A, B

Upvotes: 0

templatetypedef
templatetypedef

Reputation: 372784

No, this approach will not necessarily work. Consider the following graph:

  A ---> C
 ^ |
 | |
 | v
  B

Let's try running your proposed algorithm. We'll begin running the DFS at node A, and whenever we have a choice of which node to visit next, we'll pick the alphabetically first. The DFS will look like this:

  • Begin exploring A.
    • Begin exploring B.
      • Finish exploring B.
    • Begin exploring C.
      • Finish exploring C.
  • Finish exploring A.

That gives us the finishing times as B, C, A.

If we now run a DFS in the original graph, going in the order of finishing times, our first DFS will be from node B. That will find nodes A, B, and C, and so we'd incorrectly conclude that {A, B, C} is a strongly connected component of the graph, even though the SCCs here are actually {A, B} and C.

We could then ask - why doesn't this work? That is, what's so special about going in reverse? The answer is that if we run a DFS and record the finishing times of the nodes, the first node visited in each SCC will have the last finishing time of all the nodes in the SCC. That's why the very last node we find in the ordering must be in a source SCC, for example. On the other hand, the finishing times of the other nodes in the SCCs are not guaranteed to have any particular properties. (That's how I found this graph - I constructed it so that the first node to finish in one of the SCCs would be sequenced before a node in one of the sink SCCs).

Upvotes: 1

Related Questions