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 time proportional to V + E (in the worst case), where V is the number of vertices and E is the number of edges. Afterwards, the hasCycle operation takes constant time; the cycle operation takes time proportional to the length of the cycle.
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. |
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