Strongly connected components: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| (2 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
== Basic definitions == | |||
# [[Basic graph definitions]] | |||
== Input == | == Input == | ||
| Line 5: | Line 9: | ||
== 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]] | ||
Latest revision as of 19:07, 9 November 2014
Basic definitions
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.