Strongly connected components: Difference between revisions
Jump to navigation
Jump to search
(Created page with "== Definition == Let <math>G=(V,A)</math> be a directed graph. Consider the following equivalence relation on the nodes: <math>v\in V</math> and <...") |
No edit summary |
||
| (10 intermediate revisions by 4 users not shown) | |||
| Line 1: | Line 1: | ||
== | == Basic definitions == | ||
# [[Basic graph definitions]] | |||
== Input == | == Input == | ||
| Line 9: | Line 9: | ||
== Output == | == Output == | ||
A set of sets of nodes. Each set of nodes contains exactly the nodes of one 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 == | |||
# [[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.