A common problem which one needs to solve when dealing with graphs is to determine whether a given graph $G$ contains a cycle or not. As an example, one way to implement Kruskal's algorithm to compute the minimum spanning tree (MST) of a graph requires us to prevent the existence of cycles in the computed MST by manually detecting them and rooting them out as the MST is constructed (this version of Kruskal's algorithm does not use the union-find data structure). This post describes how one can detect the existence of cycles on undirected graphs (directed graphs are not considered here).

In what follows, a graph is allowed to have parallel edges and self-loops. On both cases, the graph has a trivial cycle. Our cycle detection algorithm will be written in Python, but implementing it in other languages should not be a difficult task if you understand the description given below. You can download the code shown in this post by clicking here.

Let's first start by introducing a simple implementation of a graph class which we will use later. A very simple class which contains all the functionality we need is defined below (it is based on the one presented here). This class does not explicitly store a list of vertices. Instead, it stores a dictionary (self.neighbors) which contains, for each vertex $v$, a list of its neighbors. A list of all vertices of the graph can be easily obtained from the keys of this dictionary, as shown in the member function vertices() below.

class graph:

	def __init__(self):
		self.neighbors = {}

	def add_vertex(self, v):
		if v not in self.neighbors:
			self.neighbors[v] = []

	def add_edge(self, u, v):
		self.neighbors[u].append(v)
		# if u == v, do not connect u to itself twice
		if u != v:
			self.neighbors[v].append(u)

	def vertices(self):
		return list(self.neighbors.keys())

	def vertex_neighbors(self, v):
		return self.neighbors[v]

Now we can proceed to detecting cycles. For undirected graphs, the algorithm is quite simple: start by selecting some unexplored vertex $v$ of $G$ and use breadth-first search (BFS) to explore every vertex which is reachable from $v$. We will refer to the set of vertices which are at a distance $n$ from $v$ simply as "the $n$-th layer". If a cycle exists, then one of the following will eventually happen as BFS progresses:

Consider case 1 first. If $u$ discovers $z$ first, it will set its layer value to $\textrm{layer}(u)+1 = n+1$. When $w$ discovers $z$, it will see that $z$ has a layer value large than $\textrm{layer}(w) = n$. Consider now case 2. In this case, some vertex $u$ from layer $n$ will find another vertex $w$ also on layer $n$, meaning $\textrm{layer}(u) = \textrm{layer}(w) = n$. Both cases lead us to immediately conclude the graph has a cycle.

(a)

(b)

The analysis above suggests we should do the following while going over the edges incident on vertices on the $n$-th layer to discover vertices on the $(n+1)$-th layer: if an edge connects the $n$-th layer vertex to an unexplored vertex, set the layer value of the unexplored vertex to $(n+1)$. If the edge leads to an already explored vertex, we must consider three possible cases:

In order to detect cycles also on disconnected graphs, we must go over every unexplored vertex $v$ and proceed as above. Every vertex which is reachable from a chosen starting vertex $v$ will not be used later as a starting point because it will be marked as explored by then. If $G$ is disconnected, some vertices will not be explored when we do BFS starting from the first unexplored vertex $v$, but as we go over the unexplored vertices in the main loop, we will eventually find every connected component of $G$.

Enough with the abstract talk. The function below implements the algorithm we just discussed and returns True if the input graph $G$ has a cycle or False otherwise:

def is_cyclic_graph(G):

	Q = []
	V = G.vertices()

	# initially all vertices are unexplored
	layer = { v: -1 for v in V }

	for v in V:

		# v has already been explored; move on
		if layer[v] != -1:
			continue

		# take v as a starting vertex
		layer[v] = 0
		Q.append(v)

		# as long as Q is not empty
		while len(Q) > 0:

			# get the next vertex u of Q that must be looked at
			u = Q.pop(0)

			C = G.vertex_neighbors(u)

			for z in C:
				# if z is being found for the first time
				if layer[z] == -1:
					layer[z] = layer[u] + 1
					Q.append(z)
				elif layer[z] >= layer[u]:
					return True

	return False

As for the run-time complexity of the algorithm, notice that each edge is considered at most twice (once for each of its end vertices), and since we go over every vertex of the graph, the overall complexity is $O(m + n)$, with $m$ and $n$ being the number of edges and vertices respectively.