public class Cycle extends Object
Cycle
class 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 |
---|
Cycle(Graph G)
Determines whether the undirected graph
G has a cycle and,
if so, finds such a cycle. |
Modifier and Type | Method and Description |
---|---|
Iterable<Integer> |
cycle()
Returns a cycle in the graph
G . |
boolean |
hasCycle()
Returns true if the graph
G has a cycle. |
static void |
main(String[] args)
Unit tests the
Cycle data type. |
public Cycle(Graph G)
G
has a cycle and,
if so, finds such a cycle.G
- the undirected graphpublic boolean hasCycle()
G
has a cycle.true
if the graph has a cycle; false
otherwisepublic Iterable<Integer> cycle()
G
.G
has a cycle,
and null
otherwisepublic static void main(String[] args)
Cycle
data type.args
- the command-line arguments