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.

Maze

A maze of 30 cells in five rows, A to E, and six columns, 1 to 6, so C4 is row C, column 4. Each edge is an open passage between two cells. The way from A1 to E6 winds through most of the maze, and two short loops give a few cells a second route.

An undirected graph with 30 vertices and 31 edges.

Is there a loop in the maze, a way to walk around and come back to a cell without going back along a passage?

Yes, the graph has a cycle: there are two different ways between some pair of vertices.

Step by step

HasCycle searches breadth-first from each vertex no earlier search has reached, in the graph's vertex order, and remembers the vertex it reached each one from. Each edge is stored in both directions, so the edge back to that vertex is the same edge and is skipped. Any other edge to a vertex already reached closes a cycle.
Start at A1, the first vertex. Put it in the queue.
Take A1 from the front of the queue. A2 is new, so it joins the back of the queue.
Take A2 from the front of the queue. The edge back to A1, which the search reached it from, is the same edge, so it is skipped. A3 is new, so it joins the back of the queue.
Take A3 from the front of the queue. The edge back to A2 is skipped. B3 is new, so it joins the back of the queue.
Take B3 from the front of the queue. The edge back to A3 is skipped. B2 is new, so it joins the back of the queue.

13 more steps lead to the last one:

D4 also has an edge to C4, which the search already reached another way. The two ways back to where they meet and this edge make a cycle: D4 → E4 → E3 → D3 → C3 → C4 → D4. 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