Cycle detection

Says whether a graph has a cycle, a way to follow its edges from a vertex back to the same vertex, and stops at the first one it finds.

Time complexity O(V+E), gograph function gograph.HasCycle.

connectivity.HasCycle gives the same answer, because it calls gograph.HasCycle.

How it works

A cycle is a way to follow the edges from a vertex and come back to it. A directed graph with a cycle has no topological order, so a build tool checks for one before it orders anything: packages that import each other in a loop can't be built one after the other.

On a directed graph, gograph searches depth-first and keeps the vertices on the current search path. An edge to a vertex that is still on the path leads back to where the path passed before, so it closes a cycle. An edge to a vertex the search has already finished can't, since nothing after that vertex leads back to the path.

On an undirected graph, gograph searches breadth-first and remembers the vertex it reached each vertex from. Each edge is stored in both directions, so the edge back to that vertex is the same edge and doesn't count. Any other edge to a vertex already reached gives a second way between two vertices, which is a cycle.

The search stops at the first cycle, and costs O(V+E) at most. A graph created with gograph.Acyclic refuses every edge that would close a cycle, so HasCycle returns false for it without a search. HasCycle only says yes or no. To list the vertices of every cycle, use the strongly connected components.

Import cycles

Eighteen packages of a Python web app. Each edge is an import, and some packages import each other in a loop.

A directed graph with 18 vertices and 30 edges.

Can these packages be built one after the other, or do some of them import each other in a loop?

Yes, the graph has a cycle: following the edges from some vertex leads back to it. So no order of the vertices puts every edge forward, and a topological sort would fail.

Step by step

1. HasCycle searches depth-first from each vertex no earlier search has reached, in the graph's vertex order, and keeps the vertices on the current search path. An edge to a vertex still on the path closes a cycle, and the search stops there.
2. Start at main, the first vertex. It goes on the search path.
3. Follow main to cli, which goes on the search path.
4. Follow cli to config, which goes on the search path.
5. Follow config to utils, which goes on the search path.
6. Follow utils to logging, which goes on the search path.
7. logging has an edge to utils, which is still on the search path. The path from utils to logging and this edge back make a cycle: utils → logging → utils. HasCycle returns true.

Use it in Go

fmt.Println(gograph.HasCycle(g)) // true when g has a cycle

Example graphs

• Build pipeline, 7 vertices and 9 edges
• Delivery area, 8 vertices and 12 edges
• Microservice calls, 9 vertices and 15 edges
• Import cycles, 18 vertices and 30 edges
• Maze, 30 vertices and 31 edges

More in Connectivity

• Tarjan: Finds the strongly connected components of a directed graph, the groups of vertices that can all reach each other, with one depth-first search.
• Kosaraju: Finds the strongly connected components of a directed graph with two depth-first searches, the second on the graph with every edge reversed.
• Gabow: Finds the strongly connected components of a directed graph with one depth-first search and two stacks, without the lowlink values of Tarjan's algorithm.
• Condensation: Replaces each strongly connected component with one vertex. What is left is a DAG, so it can be sorted and scheduled.
• Connected components: Splits a graph into its connected pieces, the groups of vertices joined to each other by some path, with one search per piece.

All algorithms