Strongly Connected Components

The strongly connected components or diconnected components of an arbitrary directed graph form a partition into subgraphs that are themselves strongly connected.

Parameters

$V$ : number of vertices
$E$ : number of edges

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 8 of 8 algorithms


Pearce	2016	$O(V+E)$	$O(V)$
Multistep	2014	O(V^2+E)	O(V+E) total
Path-based depth-first search Gabow	2000	$O(V+E)$	$O(V+E)$ total, $O(V)$ auxiliary
Couvreur	1999	$O(V+E)$	$O(V)$
Kosaraju's algorithm	1978	$O(V+E)$	$O(V+E)$
Path-based strong components algorithm; Dijkstra	1976	$O(V+E)$	$O(V)$
Tarjan's strongly connected components algorithm	1972	$O(V+E)$	$O(V)$
Munro’s algorithm	1971	$O(E + V \log V)$	$O(V)$

Reductions Table

Insuffient Data to display table

Other relevant algorithms

Displaying 1 of 1 other relevant algorithms