Strongly connected components: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
== Input == | == Input == | ||
| Line 9: | Line 5: | ||
== Output == | == Output == | ||
A set of sets of nodes. Each set of nodes contains exactly the nodes of one SCC. The correspndence between SCC and sets of nodes is one-to-one. | A set of sets of nodes. Each set of nodes contains exactly the nodes of one [[Basic graph definitions#Connectedness|SCC]]. The correspndence between the [[Basic graph definitions#Connectedness|SCC]] and these sets of nodes is one-to-one. | ||
== Pseudocode == | == Pseudocode == | ||
Revision as of 07:17, 3 November 2014
Input
A directed graph [math]\displaystyle{ G=(V,A) }[/math].
Output
A set of sets of nodes. Each set of nodes contains exactly the nodes of one SCC. The correspndence between the SCC and these sets of nodes is one-to-one.
Pseudocode
STRONGLY-CONNECTED-COMPONENTS(D)
STRONGLY-CONNECTED-COMPONENTS(D)
1 call DFS(D) to compute finishing times f[v] for each vertex v ∈ V
2 compute DT (w.r.t. step 3)
3 call DFS(DT), but in the main loop of DFS, consider the vertices in order of decreasing f[v] as computed in step 1
4 output the vertices of each tree in the DFS forest of step 3 as a separate strongly connected component
Known algorithms
Further information
STRONGLY-CONNECTED-COMPONENTS runs in linear time.