# Detect Cycle in Graphs

October 30, 2019 • ☕️ 1 min read

In graph theory, a **cycle** is a path of edges and vertices
wherein a vertex is reachable from itself. There are several
different types of cycles, principally a **closed walk** and
a **simple cycle**.

## Definitions

A **closed walk** consists of a sequence of vertices starting
and ending at the same vertex, with each two consecutive vertices
in the sequence adjacent to each other in the graph. In a directed graph,
each edge must be traversed by the walk consistently with its direction:
the edge must be oriented from the earlier of two consecutive vertices
to the later of the two vertices in the sequence.
The choice of starting vertex is not important: traversing the same cyclic
sequence of edges from different starting vertices produces the same closed walk.

A **simple cycle may** be defined either as a closed walk with no repetitions of
vertices and edges allowed, other than the repetition of the starting and ending
vertex, or as the set of edges in such a walk. The two definitions are equivalent
in directed graphs, where simple cycles are also called directed cycles: the cyclic
sequence of vertices and edges in a walk is completely determined by the set of
edges that it uses. In undirected graphs the set of edges of a cycle can be
traversed by a walk in either of two directions, giving two possible directed cycles
for every undirected cycle. A circuit can be a closed walk allowing repetitions of
vertices but not edges; however, it can also be a simple cycle, so explicit
definition is recommended when it is used.

## Example

A graph with edges colored to illustrate **path** `H-A-B`

(green), closed path or
**walk with a repeated vertex** `B-D-E-F-D-C-B`

(blue) and a **cycle with no repeated edge** or
vertex `H-D-G-H`

(red)

### Cycle in undirected graph

### Cycle in directed graph