public class EdgeWeightedDirectedCycle extends Object
EdgeWeightedDirectedCycleclass represents a data type for determining whether an edge-weighted digraph has a directed cycle. The hasCycle operation determines whether the edge-weighted digraph has a directed cycle and, if so, the cycle operation returns one.
This implementation uses depth-first search. The constructor takes Θ(V + E) time 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 Θ(V) extra space (not including the edge-weighted digraph).
Topological to compute a topological order if the
edge-weighted digraph is acyclic.
For additional documentation, see Section 4.4 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
|Constructor and Description|
Determines whether the edge-weighted digraph
|Modifier and Type||Method and Description|
Returns a directed cycle if the edge-weighted digraph has a directed cycle, and
Does the edge-weighted digraph have a directed cycle?
Unit tests the
public EdgeWeightedDirectedCycle(EdgeWeightedDigraph G)
Ghas a directed cycle and, if so, finds such a cycle.
G- the edge-weighted digraph
public boolean hasCycle()
trueif the edge-weighted digraph has a directed cycle,
public Iterable<DirectedEdge> cycle()
public static void main(String args)
args- the command-line arguments