public class Cycle extends Object
Cycleclass represents a data type for determining whether an undirected graph has a simple cycle. The hasCycle operation determines whether the graph has a 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. (The depth-first search part takes only O(V) time; however, checking for self-loops and parallel edges takes Θ(V + E) time in the worst case.) Each instance method takes Θ(1) time. It uses Θ(V) extra space (not including the graph).
For additional documentation, see Section 4.1 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
|Constructor and Description|
Determines whether the undirected graph
|Modifier and Type||Method and Description|
Returns a cycle in the graph
Returns true if the graph
Unit tests the
public Cycle(Graph G)
Ghas a cycle and, if so, finds such a cycle.
G- the undirected graph
public boolean hasCycle()
Ghas a cycle.
trueif the graph has a cycle;
Ghas a cycle, and
public static void main(String args)
args- the command-line arguments