NIST

cycle

(definition)

Definition: A path that starts and ends at the same vertex and includes at least one edge.

Generalization (I am a kind of ...)
path.

Specialization (... is a kind of me.)
Hamiltonian cycle, Euler cycle.

Aggregate parent (I am a part of or used in ...)
graph.

See also circuit (2).

Note: Also known as "circuit" or "closed path".

A cycle includes 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


Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 24 August 2017.
HTML page formatted Fri Feb 23 10:06:07 2018.

Cite this as:
Paul E. Black, "cycle", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 24 August 2017. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/cycle.html