Talk:Strongly connected component

Mathematics Stub‑class Low‑priority

	Mathematics portal This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics articles
Stub	This article has been rated as Stub-class on Wikipedia's content assessment scale.
Low	This article has been rated as Low-priority on the project's priority scale.

There is also an algorithm called SCC that computes strongly connected components in graphs, by taking the inverse of a graph and working on the transpose G^t (V, E^-1) of G. Would it help if I put the pseudocode algorithm in here? Jontce 11:08, 17 May 2005 (UTC)[reply]
Isn't this a dictionary definition? At least, it should be linked to something else. m.e. 10:40, 28 May 2004 (UTC)[reply]

This page does not render correctly in IE7

Question about the algorithm

In step 1, DFS is called on a specific vertex v.

It needs to visit every vertex in the (weakly) connected component that v belongs to, to compute its finishing time.

In a directed graph, how can we choose the start node v for DFS in such a way as to visit every node in the weakly connected component of v and not add to the total complexity of the algorithm? This does not seem obvious to me. Thanks if you can explain this.

- Panayk (talk) 16:40, 18 January 2008 (UTC)[reply]

Nevermind. DSF is called on more than one starting vertices, taking care not to call it on (or revisit during a call) an already visited vertex. Perhaps we should mention that.

- Panayk (talk) 18:16, 18 January 2008 (UTC)[reply]

Algorithm

The algorithm section seems to be lifted word-for-word from CLR...