Cycle (graph theory)
≈ 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.