Finding Components in a Directed Graph

The second thing I've learnt today is about finding strongly connected components in a directed graph. A strongly connected component is one in which there exists a directed path between every pair of vertices in each direction.

The algorithm in involves starting with an ordering (any ordering) of the vertices, running a depth first search on the graph with all arcs reversed, while keeping note of position the vertices are removed from the stack. This position is then used to order the vertices in the original graph. A second depth first search is run, this time on the original graph with the new ordering of the vertices from largest to smallest. Whichever vertices are generated from the same leader are in the same component.

Example

For the directed graph above, I'll run through the algorithm. First we reverse all the arcs like this:

Starting at 1, we do a depth first search on the graph. From 1 we can go to 2 or 4, and we arbitarily pick 4. From 4 we can go to 10 or 6 so we'll go for 10. From 10 we have no choice but to go to 7, then 8 and from there to 9 and then 3. From 3 we have no unvisited vertex to add so 3 pops off the stack and gets new label 1. I'll use f(3)=1 to denote the new label of vertex 3.

1-> 4 -> 10 ->7-> 8->9->3 dead end so f(3)=1.
1->4->10->7->8->9 dead end so 9 pops off next giving vertex 9 the new label 2, that is, f(9)=2.
1->4->10->7->8 dead end so 8 pops off giving f(8)=3.
1->4->10->7 dead end so 7 pops off giving f(7)=4.
1->4->10 dead end so 10 pops off giving f(10)=5.
1->4    this time it isn't a dead end so we take the other option at 4 which is 6, then 5.
1->4->6 ->5  dead end since 1 has already been visited so 5 pops off giving f(5)=6.
1->4->6  dead end so f(6)=7.
1->4 dead end so f(4)=8.
1  not a dead end as we haven't yet visited 2.
1->2 but since 10 has already been visited this is a dead end. Thus f(2)=9.
1 dead end and finally 1 pops off giving f(1)=10.
Since all vertices have been visited, we're done with the first DFS. The original graph with the new ordering of vertices is shown below.

Starting at 10, we do a depth first search again, taking note of the leader vertex for each vertex, that is, the vertex which starts the path containing that vertex.

10-> 6->7->8.  Now  8 pops off then 7 then 6 and finally 10. All of these have leader vertex 10 and thus are in the same strongly connected component as 10.
The next unvisited vertex is 9, so we start the next path with 9. There is no unvisited vertex accessible from 9 so it's in a component on its own.
Now we move on to 5.
5->1->2->3->4.  Each of these vertices pops off, 4 then 3, 2, 1, 5. All of them have lead vertex 5 so are in the same strongly connected component..

All vertices have been visited so we are done with the second DFS. This leaves us with the following three components. Note that vertex 9 is in a component on its own and not the same component as 1,2,3,4,5.

Source
CS 161 - Design and Analysis of Algorithms Lectures 6