Talk:Strongly connected component

Computing Stub‑class

	This article is within the scope of WikiProject Computing, a collaborative effort to improve the coverage of computers, computing, and information technology 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.ComputingWikipedia:WikiProject ComputingTemplate:WikiProject ComputingComputing
Stub	This article has been rated as Stub-class on Wikipedia's content assessment scale.
???	This article has not yet received a rating on the project's importance scale.
	This article has been automatically rated by a bot or other tool as Stub-class because it uses a stub template. Please ensure the assessment is correct before removing the `\|auto=` parameter.

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
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

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... —Preceding unsigned comment added by 67.114.158.146 (talk) 08:05, 9 April 2008 (UTC)[reply]

Is the image correct?

I see that C and H are not connected, is that correct? —Preceding unsigned comment added by 128.61.23.186 (talk) 19:36, 5 June 2008 (UTC)[reply]

yes, it is ok. They don't need to be directly connected by edges. --Fioravante Patrone en (talk) 20:08, 21 August 2008 (UTC)[reply]

I think he's right, since the definition is a PATH between two points. C can get to H and vice versa over a path. It's the fact that you can go both ways that makes that group strongly connected Delvarworld (talk) 08:22, 17 April 2011 (UTC)[reply]

Definition

The current definition (and the example) of a strongly connected component subtly avoids the delicate question whether a singleton node without selfloop is strongly connected or not.--94.221.120.119 (talk) 19:46, 22 January 2012 (UTC)[reply]

It does sort of avoid the question, but I think the only reasonable choice is to count a single node (without selfloop) as strongly connected to itself, by paths of lengths zero. For otherwise, it would not be true that strong connectivity is an equivalence relation and that the strongly connected components form a partition of any graph's vertices. —David Eppstein (talk) 22:30, 22 January 2012 (UTC)[reply]