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.

Build pipeline

The jobs of a CI pipeline for a web service, and how many minutes each one takes. Each edge points from a job to a job that waits for it.

A directed graph with 7 vertices and 9 edges.

Can these jobs run in some order, or do some of them wait on each other in a loop?

No, the graph has no cycle. Following the edges never leads back to where it started, so the vertices can be put in an order where every edge points forward.

Step by step

1. The graph was created with gograph.Acyclic, which refuses any edge that would close a cycle. So HasCycle returns false without a search.

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