Editing Cycle (graph theory) (section)

== Cycle detection ==
The existence of a cycle in directed and undirected graphs can be determined by whether a [[depth-first search]] (DFS) finds an edge that points to an ancestor of the current vertex (i.e., it contains a [[Depth-first search#Output of a depth-first search|back edge]]).<ref>{{cite book|last=Tucker|first=Alan|author-link=Alan Tucker|title=Applied Combinatorics |year=2006|publisher=John Wiley & sons|location=Hoboken|isbn=978-0-471-73507-6|edition=5th|page=49|chapter=Chapter 2: Covering Circuits and Graph Colorings}}</ref> All the back edges which DFS skips over are part of cycles.<ref name="sedgewick">{{citation | first=Robert | last=Sedgewick | author-link=Robert Sedgewick (computer scientist) | title=Algorithms | chapter=Graph algorithms | year=1983 | publisher=Addison–Wesley | isbn=0-201-06672-6 | url-access=registration | url=https://archive.org/details/algorithms00sedg }}</ref> In an undirected graph, the edge to the parent of a node should not be counted as a back edge, but finding any other already visited vertex will indicate a back edge. In the case of undirected graphs, only ''O''(''n'') time is required to find a cycle in an ''n''-vertex graph, since at most ''n''&nbsp;−&nbsp;1 edges can be tree edges.

Many [[topological sorting]] algorithms will detect cycles too, since those are obstacles for topological order to exist. Also, if a directed graph has been divided into [[strongly connected component]]s, cycles only exist within the components and not between them, since cycles are strongly connected.<ref name="sedgewick" />

For directed graphs, distributed message-based algorithms can be used. These algorithms rely on the idea that a message sent by a vertex in a cycle will come back to itself.
Distributed cycle detection algorithms are useful for processing large-scale graphs using a distributed graph processing system on a [[computer cluster]] (or supercomputer).

Applications of cycle detection include the use of [[wait-for graph]]s to detect [[deadlock (computer science)|deadlock]]s in concurrent systems.<ref>{{cite book
  | last = Silberschatz
  | first = Abraham
  |author2=Peter Galvin |author3=Greg Gagne
   | title = Operating System Concepts
  | url = https://archive.org/details/operatingsystemc0006silb
  | url-access = registration
  | publisher = John Wiley & Sons, INC.
  | year = 2003
  | pages = [https://archive.org/details/operatingsystemc0006silb/page/260 260]
  | isbn = 0-471-25060-0}}</ref>

=== Algorithm ===
The aforementioned use of depth-first search to find a cycle can be described as follows:
 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.