Strongly connected components: Difference between revisions

From Algowiki
Jump to navigation Jump to search
No edit summary
No edit summary
Line 6: Line 6:


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.
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 ==
====STRONGLY-CONNECTED-COMPONENTS(''D'')====
<code>
STRONGLY-CONNECTED-COMPONENTS(''D'')
1 call '''DFS'''(''D'') to compute finishing times ''f''[v] for each vertex ''v'' &isin; ''V''
2 compute ''D''<sup>''T''</sup> (w.r.t. step 3)
3 call '''DFS'''(''D''<sup>''T''</sup>), 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
</code>


== Known algorithms ==
== Known algorithms ==


# [[Kosaraju]]
# [[Kosaraju]]
== Further information ==
''STRONGLY-CONNECTED-COMPONENTS'' runs in linear time.

Revision as of 07:19, 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.

Known algorithms

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