Understanding cycle detection in an undirected graph

Graphs are composed of nodes connected via edges and are not restricted by any specific topology. Unlike a tree, which is a specialised graph as it is acyclic, a general graph can have cycles. A cycle in a graph is a path that starts and ends at the same node, has no repeated edges, and has at least three nodes. In this lesson, we will look at cycles in undirected graphs and learn the algorithm that can be used to detect such cycles.

Algorithm

Detecting a cycle in an undirected graph is quite simple. We can piggyback on any traversal algorithm, like depth-first or breadth-first traversal, while keeping track of visited nodes. If we ever revisit a node during traversal, it means a cycle exists in the graph. We will learn more about the proof of correctness later in the lesson. In this explanation, we will use depth-first traversal to detect a cycle, as it is a simpler, more concise implementation.

We begin by creating a visited set to keep track of the nodes that have been visited. We then iterate through the list of nodes and for each node, check if it is already visited. If it is visited, we ignore it and proceed to the next node; otherwise, we perform a depth-first traversal from the node to detect if it is part of any cycle using a cycle detection function.

The cycle detection function is a slightly modified depth-first traversal algorithm that exits as soon as it detects a cycle. It accepts the identifier of the current node, the identifier of the parent node and the visited set as arguments, where the visited set is passed by reference. We pass the parent node to filter out the parent node from the neighbours, as undirected edges can be traversed both ways. Since the first node where the depth-first traversal starts does not have a parent, we pass a sentinel value that will never be a node identifier as the parent.