Cycle (Graph)

graph-theory algorithms

Definition

Cycle

In graph theory, a cycle is a non-empty path in which only the first and last vertices are equal. A graph that contains no cycles is called an acyclic graph.

Formally, a cycle in an undirected graph is a sequence of vertices $v_1,v_2,\dots ,v_n$ such that $(v_i,v_{i+1})$ is an edge for $1\le i<n$,$v_1=v_n$, and $n>3$. For a directed graph, the sequence is called a directed cycle.

Visual Representation

Properties and Related Concepts

• Tree: A connected graph is a tree if and only if it is acyclic.
• Directed Acyclic Graph (DAG): A directed graph with no directed cycles.
• Cycle Detection: Algorithms such as Depth-First Search (DFS) can be used to detect cycles in $O(|V|+|E|)$ time. In undirected graphs, the Union-Find data structure is also commonly employed.
• Girth: The length of a shortest cycle in a graph.