Cycle (graph theory)

Uses your system voice; voice and rate in settings.

Snapshot

≈ 3 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

, H–A–B–A–H, in green; a circuit which is a closed walk in which all edges are distinct, B–D–E–F–D–C–B, in blue; and a cycle which is a closed walk in which all vertices are distinct, H–D–G–H, in red. In graph theory, a cycle in a graph is a non-empty trail in which only the first and last vertices are equal. A directed cycle in a directed graph is a non-empty directed trail in which only the first and last vertices are equal. A graph without cycles is called an acyclic graph (or a forest). A directed graph without directed cycles is called a directed acyclic graph. A connected graph without cycles is called a tree.

, H–A–B–A–H, in green; a circuit which is a closed walk in which all edges are distinct, B–D–E–F–D–C–B, in blue; and a cycle which is a closed walk in which all vertices are distinct, H–D–G–H, in red. In graph theory, a cycle in a graph is a non-empty trail in which only the first and last vertices are equal. A directed cycle in a directed graph is a non-empty directed trail in which only the first and last vertices are equal. A graph without cycles is called an acyclic graph (or a forest).

A directed graph without directed cycles is called a directed acyclic graph. A connected graph without cycles is called a tree. For every vertex v: visited(v) = finished(v) = false For every vertex v: DFS(v) where DFS(v) = if finished(v): return if visited(v): "Cycle found" return visited(v) = true for every neighbour w: DFS(w) finished(v) = true For undirected graphs, "neighbour" means all vertices connected to v, except for the one that recursively called DFS(v).

This omission prevents the algorithm from finding a trivial cycle of the form v→w→v; these exist in every undirected graph with at least one edge. A variant using breadth-first search instead will find a cycle of the smallest possible length.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1372590600 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

7 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.