(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

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

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

Entry modified 4 November 2009.

HTML page formatted Fri Mar 25 16:20:34 2011.

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. 4 November 2009. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/cycle.html