Package edu.princeton.cs.algs4
Class EdgeWeightedDirectedCycle
 Object

 edu.princeton.cs.algs4.EdgeWeightedDirectedCycle

public class EdgeWeightedDirectedCycle extends Object
TheEdgeWeightedDirectedCycle
class represents a data type for determining whether an edgeweighted digraph has a directed cycle. The hasCycle operation determines whether the edgeweighted digraph has a directed cycle and, if so, the cycle operation returns one.This implementation uses depthfirst 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 edgeweighted digraph).
See
Topological
to compute a topological order if the edgeweighted digraph is acyclic.For additional documentation, see Section 4.4 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
 Author:
 Robert Sedgewick, Kevin Wayne


Constructor Summary
Constructors Constructor Description EdgeWeightedDirectedCycle(EdgeWeightedDigraph G)
Determines whether the edgeweighted digraphG
has a directed cycle and, if so, finds such a cycle.

Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description Iterable<DirectedEdge>
cycle()
Returns a directed cycle if the edgeweighted digraph has a directed cycle, andnull
otherwise.boolean
hasCycle()
Does the edgeweighted digraph have a directed cycle?static void
main(String[] args)
Unit tests theEdgeWeightedDirectedCycle
data type.



Constructor Detail

EdgeWeightedDirectedCycle
public EdgeWeightedDirectedCycle(EdgeWeightedDigraph G)
Determines whether the edgeweighted digraphG
has a directed cycle and, if so, finds such a cycle. Parameters:
G
 the edgeweighted digraph


Method Detail

hasCycle
public boolean hasCycle()
Does the edgeweighted digraph have a directed cycle? Returns:
true
if the edgeweighted digraph has a directed cycle,false
otherwise

cycle
public Iterable<DirectedEdge> cycle()
Returns a directed cycle if the edgeweighted digraph has a directed cycle, andnull
otherwise. Returns:
 a directed cycle (as an iterable) if the edgeweighted digraph
has a directed cycle, and
null
otherwise

main
public static void main(String[] args)
Unit tests theEdgeWeightedDirectedCycle
data type. Parameters:
args
 the commandline arguments

