public class KosarajuSharirSCC extends Object
KosarajuSharirSCC
class represents a data type for
determining the strong components in a digraph.
The id operation determines in which strong component
a given vertex lies; the areStronglyConnected operation
determines whether two vertices are in the same strong component;
and the count operation determines the number of strong
components.
The component identifier of a component is one of the vertices in the strong component: two vertices have the same component identifier if and only if they are in the same strong component.
This implementation uses the Kosaraju-Sharir algorithm.
The constructor takes Θ(V + E) time,
where V is the number of vertices and E
is the number of edges.
Each instance method takes Θ(1) time.
It uses Θ(V) extra space (not including the digraph).
For alternative implementations of the same API, see
TarjanSCC
and GabowSCC
.
For additional documentation, see Section 4.2 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
Constructor and Description |
---|
KosarajuSharirSCC(Digraph G)
Computes the strong components of the digraph
G . |
Modifier and Type | Method and Description |
---|---|
int |
count()
Returns the number of strong components.
|
int |
id(int v)
Returns the component id of the strong component containing vertex
v . |
static void |
main(String[] args)
Unit tests the
KosarajuSharirSCC data type. |
boolean |
stronglyConnected(int v,
int w)
Are vertices
v and w in the same strong component? |
public KosarajuSharirSCC(Digraph G)
G
.G
- the digraphpublic int count()
public boolean stronglyConnected(int v, int w)
v
and w
in the same strong component?v
- one vertexw
- the other vertextrue
if vertices v
and w
are in the same
strong component, and false
otherwiseIllegalArgumentException
- unless 0 <= v < V
IllegalArgumentException
- unless 0 <= w < V
public int id(int v)
v
.v
- the vertexv
IllegalArgumentException
- unless 0 <= s < V
public static void main(String[] args)
KosarajuSharirSCC
data type.args
- the command-line arguments