Find a cycle

Returns the vertices of one cycle in order: the first one a depth-first search closes with an edge back to its search path.

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

How it works

Cycle detection says whether a graph has a cycle. FindCycle also says where: it returns the vertices of one cycle in order, so a build tool can tell which packages import each other in a loop instead of only that some do.

It runs traverse.DFSEventsAll, a depth-first search from each vertex no earlier search reached, and keeps the search path. An edge to a vertex that is still on the path is a back edge: the path runs from that vertex down to the one the search is at, and the edge leads back up, so together they are a cycle. FindCycle returns that part of the path at the first back edge. An edge to a finished vertex can't close a cycle, since nothing that vertex leads to reaches back to the path.

On an undirected graph, the edge back to the vertex a vertex was reached from is the same edge seen from the other end, so it doesn't count, and every other cycle has at least three vertices. A self-loop is a cycle of one vertex.

The search stops at the first back edge and costs O(V+E) at most. The cycle it returns is the first one it closes, not the shortest one. A graph created with gograph.Acyclic returns false without a search. To list every vertex that is on some 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.

Find a loop in the maze: a way around that comes back to a cell without going back along a passage.

FindCycle returns a cycle of 4 vertices: B6 – B5 – C5 – C6 – B6. It is the first cycle the search closes, and the graph can have others.

Step by step

  1. FindCycle 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. The first edge to a vertex still on the path closes a cycle. On an undirected graph, the edge back to the vertex a vertex was reached from doesn't count.
  2. Start at A1, the first vertex in the graph's order. It begins the search path.
  3. Follow A1 to A2, a new vertex. A2 joins the search path.
  4. A2 to A1 leads back to A1, the vertex A2 was reached from. That is the same edge seen from the other end, so it doesn't count, here or anywhere else it comes up.
  5. Follow A2 to A3, a new vertex. A3 joins the search path.
  6. Follow A3 to B3, a new vertex. B3 joins the search path.

23 more steps lead to the last one:

  1. Done. FindCycle returns the 4 vertices of the cycle in order, starting where the back edge leads. The search stopped at the first cycle it closed, and a shorter one can exist.

Use it in Go

cycle, ok := connectivity.FindCycle(g)
if !ok {
	return // no cycle
}
for _, v := range cycle {
	fmt.Print(v.Label(), "->")
}
fmt.Println(cycle[0].Label())

Example graphs

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.
  • 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.
  • Bridges and articulation points: Finds the edges and the vertices whose loss splits an undirected graph into more pieces, its single points of failure, from one depth-first search.

All algorithms