Topological Sort and Strongly Connected Components
A topological sort on a Graph G(V,E) is a arrangement of its nodes so that all the edges point from left to right. This can be useful in cases where say there is a ordering of a certain set of events and such events are repressented by a directed edge from node u to v if u occurs before v. Now if we want to have an arrangement of node so that they are ordered as written above we use the following algorithm :
TopologicalSort(G)
1.Run DFS on the Grpah 2.Whenever a node is "finished" immediately place it in a linked list. 3. return the list
This algo works because a node which is first finished is put into the list and the next finshed node is put in next. The last node to finish will be on top of the list and this will be the left most event.
Strongly Connected Components
A strongly connected component of a digraph is a MAXIMAL set of vertices C such that for every pair of vertices there is a path from u to v and from v to u.
We can make use of DFS to find the SCCs of a digraph using the following algortihm
SCC(G)
1.Run DFS on the graph 2. Compute Gt(the transpose graph) 3.Run DFS on Gt in order of decreasing finish time 4. Return the trees formed in DFS
SCCs are very useful in reducing complex graphs into a set of relevant nodes. We can collapse all nodes in a SCC to make our analysis of graphs easier.
Adapted from Cormen,Leiserson , Rivest and Stein and EE608 notes (Spring 2008)
