Detailed explanation of kosaraju algorithm

What does kosaraju algorithm do?

Kosaraju algorithm can calculate the strongly connected components of a directed graph

What is a strongly connected component?

In a directed graph, if two nodes (node V and node w) are in the same ring (equivalent to that V can reach w through a directed path, and W can also reach V), they are strongly connected. All strongly connected points form a set. The number of such sets in a directed graph is the number of strongly connected components of the graph

How??

Step 1: calculate the inverse postorder arrangement of the inverse graph (g inverse) of the directed graph (g) (introduced in the code)

Step 2: carry out standard depth first search in the directed graph (g), and arrange it according to the reverse order just calculated instead of the standard order

Why can we calculate the number of strongly connected components in this way? (slightly puzzling)

For example, there is a graph with five strongly connected components

We need to prove that ① found in the DFS (Temp) of line 26 is all the strong connected points of point temp, and ② is all its strong connected points

When proving, don't forget to define: V can reach w through a directed path, and W can also reach V, then they are strongly connected

First prove ②:

With the method of counter proof, if a strong connected point (point v) of a point (point w) is not found during the depth first search.

If it is not found, it means that point v has been marked when looking for other points, but if point v has been marked, because there is a directed path of V - > W, point w must also be found, so the depth of point w will not be searched first.

Assumption does not hold (*^ ω^*)

Re certification ①:

A point (point v) is found during the depth first search of a point (point w), indicating that there is a directed path of W - > V. It is enough to prove that there is a path of V - > W. proving that there is a path of V - > W is equivalent to proving the reverse graph of graph G (g) there is a directed path of W - > V, because point W and point v satisfy the inverse postorder arrangement, and the inverse postorder arrangement is to add nodes to the stack at the end of redfs (node) and pop them up from the stack, which indicates that redfs (V) must end before redfs (W) in the depth first search of the inverse graph. That is two cases:

■ redfs (V) is over and redfs (W) starts

■ redfs (V) ends after redfs (W) starts and before it ends, that is, redfs (V) ends inside redfs (W)

The first case is impossible because G has a path of V - > W (because G has a path of W - > V), which satisfies the second case, that is, there is a path of W - > V in G.

It's over at last.

Full code:

The above is the whole content of this article. I hope it will be helpful to your study, and I hope you can support programming tips.