Since I’m reading about algorithms, I figured I’d review topological sort and Kosaraju’s algorithm as well.
To sort vertices in a directed graph topologically is to arrange them into a sequence so that no vertex has an edge pointing to a vertex earlier in that sequence. Of course, this requires the graph to be DAG (directed acyclic graph).
The algorithm is simply to find the reverse postorder in DFS (depth first search) of the vertices. This is implemented by pushing a vertex into a stack after its DFS call completes. The order in which vertices are popped out of the stack is the graph’s reverse postorder. The proof is described below:
We need to prove that for every edge from s to v, s would appear before v in reverse postorder. There are several conditions:
- v is called and returned before the call to s. In this case, s is pushed to the stack later than v, hence s appears before v.
- v is called later than s but returned before s returns. The former conclusion also holds.
- v is called later than s has returned. This case is impossible. Since s has an edge to v, v has to be called somewhere earlier than s returns.
Therefore, our algorithm can give us a topological sort.
Next, we use a similar way to look for connected components in DAG. A connected component is defined as a subgraph in which all vertices have a way to reach each other. This algorithm is not so obvious: first get a topological order of the reverse of the graph G – Gr, then use the order to run DFS in G. All vertices reached by one call belong to a connected component, so we can mark them.
The proof also needs some brain.
Consider the second step of the algorithm. First, it is obvious every connected component edge is called in the second step, duh. Then we prove from the other side. Say we have a vertex v that is reached by calling DFS on s. We’re gonna prove there is an edge from v to s as well.
From the way we generated the order, s appears before v in reverse postorder of Gr. Now consider Gr, we have several conditions:
- the call to v ends before the call to s starts. This is impossible because v has an edge to s in Gr.
- the call to v starts after the call to s, and ends before s ends. This means there is an edge from s to v in Gr, which then proves that in G there is an edge from v to s. Connected component it is.
- the call to v starts after the call to s ends. Impossible because s appears before v in reverse postorder of Gr.
Therefore, Kosoraju’s algorithm is correct in finding connected components of DAG.
I appreciate the brilliance of the algorithms. It’s interesting because they don’t seem so hard to me now but I spent days to understand the proof the first time I read about them. I’m reading divide-and-conquer next. I’m hoping all the complicated recursions don’t play with my mind too much.