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:
1. | there will be an integer $n$ such that after we explore all vertices from the $n$-th layer and proceed to explore the vertices on the $(n+1)$-th layer, some vertex $z$ on the $(n+1)$-th layer will be reachable from two vertices $u$ and $w$ on the $n$-th layer (see figure 1a) |
2. | there will be an integer $n$ such that after we explore all vertices from the $n$-th layer and proceed to explore the vertices on the $(n+1)$-th layer, we will end up finding that two vertices $u$ and $w$ on the $n$-th layer are actually connected (see figure 1b). |
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.
Fig. 1: | One of the two possible cases which must be dealt with when detecting cycles using BFS (only the relevant edges of each graph are shown). On both figures, $v$ is the starting vertex and both $u$ and $w$ are vertices on the $n$-th layer; (a) shows the case in which $u$ and $w$ discover the same vertex $z$ on the $(n+1)$-th layer while (b) shows the case in which $u$ and $w$ discover each other. |
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:
1. | edge connects vertex on layer $n$ to a vertex on layer $(n-1)$ $\Rightarrow$ ignore it, this edge has already been taken into account |
2. | edge connects vertex on layer $n$ to another vertex on layer $n$ $\Rightarrow$ cycle detected |
3. | edge connects vertex on layer $n$ to a vertex which was already tagged as being on layer $(n+1)$ $\Rightarrow$ cycle detected |
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.
Comments
No comments posted yet.