What is a cycle

In graph theory, a path that starts from a given node and ends on the same node is a cycle.

Cycle Detection in an Undirected Graph

A graph is said to be undirected if it is bidirectional. It is a set of vertices and edges connected where edges are bidirectional.
The cycle in a graph can be detected using graph traversal algorithms. Let us discuss the cycle detection using Breadth-First Search Algorithm.

BFS Algorithm for Cycle Detection in an Undirected Graph

📌 Initialise a visited boolean array with all nodes unvisited.
Below is a disconnected graph of nodes from 0 to 9 with a queue, visited array initialised.

📌 Run a loop from 0 to 9 and start our BFS when the node is not visited.

📌 Initialise an empty queue. This queue will be holding a pair, nodes and the previous node.

📌 Mark the node as visited and add the node and previous node into the queue. At the very start, there won't be any previous node, so add {node, -1} to the queue.

📌 Until our queue is empty, repeat the following steps :
📎 Remove the node from the top of the queue.
📎 Traverse through the children of the currently removed node.
📎 If the child is not visited, mark the child as visited. Add child and the previous node, the currently removed node, to the queue.
📎 If the child is visited and the previous node = child node, continue with our BFS algorithm as it is not a cycle.
📎 If the child is visited and the previous node != child node, this means we reached our child through some other path which will result in a cycle. We stop our BFS now and return that we have detected a cycle in the graph.

📌 If we continue with our algorithm till our queue becomes empty and all the nodes become visited, this means we haven't found any cycle in the graph and return that we haven't detected any cycle in the graph.

Time and Space Complexity

We are traversing through all the nodes and edges. So time complexity will be O(V + E) where V = vertices or node, E = edges.
We use a visited array, queue, and an adjacency list for the graph. So the space complexity will be O(V) + O(V) + O(V + E). (Ignoring the space for the final result list).

Code

Originally Published on : LinkedIn Newsletter

Practice Problem

Cycle Detection in undirected graph

Github Link