Package edu.princeton.cs.algs4
Class TransitiveClosure
- Object
-
- edu.princeton.cs.algs4.TransitiveClosure
-
public class TransitiveClosure extends Object
TheTransitiveClosure
class represents a data type for computing the transitive closure of a digraph.This implementation runs depth-first search from each vertex. The constructor takes Θ(V(V + E)) in the worst case, where V is the number of vertices and E is the number of edges. Each instance method takes Θ(1) time. It uses Θ(V2) extra space (not including the digraph).
For large digraphs, you may want to consider a more sophisticated algorithm. Nuutila proposes two algorithm for the problem (based on strong components and an interval representation) that runs in Θ(E + V) time on typical digraphs. For additional documentation, see Section 4.2 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
- Author:
- Robert Sedgewick, Kevin Wayne
-
-
Constructor Summary
Constructors Constructor Description TransitiveClosure(Digraph G)
Computes the transitive closure of the digraphG
.
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description static void
main(String[] args)
Unit tests theTransitiveClosure
data type.boolean
reachable(int v, int w)
Is there a directed path from vertexv
to vertexw
in the digraph?
-
-
-
Constructor Detail
-
TransitiveClosure
public TransitiveClosure(Digraph G)
Computes the transitive closure of the digraphG
.- Parameters:
G
- the digraph
-
-
Method Detail
-
reachable
public boolean reachable(int v, int w)
Is there a directed path from vertexv
to vertexw
in the digraph?- Parameters:
v
- the source vertexw
- the target vertex- Returns:
true
if there is a directed path fromv
tow
,false
otherwise- Throws:
IllegalArgumentException
- unless0 <= v < V
IllegalArgumentException
- unless0 <= w < V
-
main
public static void main(String[] args)
Unit tests theTransitiveClosure
data type.- Parameters:
args
- the command-line arguments
-
-