Strongly connected components: Difference between revisions

From Algowiki
Jump to navigation Jump to search
No edit summary
No edit summary
 
(6 intermediate revisions by 3 users not shown)
Line 1: Line 1:
== Definition ==
== Basic definitions ==
[[File:Scc.png|300px|thumb|right|Graph with marked strongly connected components]]
 
Let <math>G=(V,A)</math> be a [[Basic graph definitions|directed graph]]. Consider the following equivalence relation on the nodes: <math>v\in V</math> and <math>w\in V</math> are equivalent if, and only if, there is a path fmo <math>v</math> to <math>w</math> and a path from <math>w</math> to <math>v</math> in <math>G</math>. The equivalence classes are called the '''strongly connected components (SCC)''' of <math>G</math>.
# [[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 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 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

  1. Basic graph 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.

Known algorithms

  1. Kosaraju
Retrieved from "https://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Strongly_connected_components&oldid=1884"