(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" or "closed path".
Author: PEB
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 30 May 2006.
HTML page formatted Mon Sep 11 09:46:02 2006.
Cite this as:
Paul E. Black, "cycle", in
Dictionary of Algorithms and Data
Structures [online], Paul E. Black, ed.,
U.S. National Institute of
Standards and Technology. 30 May 2006. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/cycle.html
