(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 Black.
Entry modified 4 November 2009.
HTML page formatted Mon Feb 2 13:10:39 2015.
Cite this as:
Paul E. Black, "cycle", in
Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 4 November 2009. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/cycle.html