Strongly connected components: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 5: | Line 5: | ||
== Output == | == Output == | ||
A set of sets of nodes. Each set of nodes contains exactly the nodes of one [[Basic graph definitions#Connectedness|SCC]]. The | A set of sets of nodes. Each set of nodes contains exactly the nodes of one [[Basic graph definitions#Connectedness|SCC]]. The correspondence between the [[Basic graph definitions#Connectedness|SCC]] and these sets of nodes is one-to-one. | ||
== Known algorithms == | == Known algorithms == | ||
# [[Kosaraju]] | # [[Kosaraju]] | ||
Revision as of 15:23, 4 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 correspondence between the SCC and these sets of nodes is one-to-one.