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.

Delivery area

Eight stops in a small town. Streets are one way, and each edge is the travel time in minutes.

A directed, weighted graph with 8 vertices and 12 edges.

Can a van that keeps to the one-way streets ever get back to a corner it has already left?

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. 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 Depot, the first vertex. It goes on the search path.
3. Follow Depot to Bakery, which goes on the search path.
4. Follow Bakery to School, which goes on the search path.
5. Follow School to Library, which goes on the search path.
6. Follow Library to Station, which goes on the search path.

11 more steps lead to the last one:

18. Done. Every vertex is finished, and no edge led back to a vertex on the search path, so HasCycle returns false.

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