(definition)
Definition: A path that starts and ends at the same vertex and includes at least one edge.
Generalization (I am a kind of ...)
(nonsimple) path.
Specialization (... is a kind of me.)
Hamiltonian cycle, Euler cycle.
Aggregate parent (I am a part of or used in ...)
graph.
Note: Also known as "circuit" or "closed path".
A cycle is usually assumed to be a simple path ignoring the start (and end) vertex. That is, it include vertices other than the start/end at most once.
Having at least one edge means that there are at least two vertices in the path: the start/end and one other. It also means the path length is at least one.
One way to find a cycle is to do a depth-first search, checking for repeated vertices. One step in finding all cycles is to look for strongly connected components.
Author: PEB
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 9 September 2008.
HTML page formatted Tue Sep 9 14:32:54 2008.
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. 9 September 2008. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/cycle.html
