Monday, September 11, 2006

Strongly Connected Components

//Strongly Connected Components

//call DFS(G) to compute finishing times f[u] for each vertex u
//compute GT, the transpose of G
//call DFS(GT), but in the main loop of DFS, consider the vertices
// in order of decreasing f[u] (as computed in line 1)
//output the vertices of each tree in the depth-first forest formed in line 3 as
// a separate strongly connect component

No comments:

Post a Comment

Please post your comment here. ;)