(definition)
Definition: A path in a graph that starts and ends at the same vertex and includes other vertices at most once. To find a cycle, use depth-first search. One step in finding all cycles is to look for strongly connected components.
Generalization (I am a kind of ...)
(nonsimple) path.
Specialization (... is a kind of me.)
Hamiltonian cycle.
See also Euler cycle.
Note: Ignoring the start (or end) vertex, the constraint that it include vertices at most once makes a cycle a simple path.
Also known as "circuit".
Author: PEB
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified Fri Dec 17 12:23:31 2004.
HTML page formatted Wed Oct 26 09:47:24 2005.
Cite this as:
Paul E. Black, "cycle", from
Dictionary of Algorithms and Data
Structures, Paul E. Black, ed.,
NIST.
http://www.nist.gov/dads/HTML/cycle.html
