Talk:Strongly connected component
From Wikipedia, the free encyclopedia
 |
|||||
| Mathematics rating: | Stub Class | Low Priority | Field: Discrete mathematics | ||
| Please update this rating as the article progresses, or if the rating is inaccurate. Please also add comments to suggest improvements to the article. | |||||
- 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)
- Isn't this a dictionary definition? At least, it should be linked to something else. m.e. 10:40, 28 May 2004 (UTC)
This page does not render correctly in IE7
[edit] 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)
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)
[edit] 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)
[edit] 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)
