Cycle Detection

Cycle detection in a graph refers to the process of identifying whether a cycle exists — a path that starts and ends at the same vertex without retracing any edge — in a given graph. The method for detecting a cycle depends on whether the graph is directed or undirected.

Cycle Detection in Undirected Graph

In an undirected graph, any path of 3+ vertices that returns to the start vertex forms a cycle. We need to keep track of the parent for every node so that we don't detect a traversal between edges as a cycle.

Approach - DFS and BFS

Start from a vertex, keep track of the visited nodes and the parent of each (since in undirected graphs, the same edge is seen twice). If a visited node is encountered again, and it is not the parent, a cycle exists. Method tracking the parent varies slighly in DFS and BFS. In DFS, you pass the current node and parent node as a part of the recursion call where as in BFS, you store them as a tuple (node, parentNode).

Undirected Graph Cycle

Medium2

261. Graph Valid TreeMedium

Undirected Graph Cycle

DFS

Interactive Visualization

Python

from collections import defaultdict


class Solution:
    def isCycle(self, V, edges):
        graph = defaultdict(list)
        for src, dst in edges:
            graph[src].append(dst)
            graph[dst].append(src)

        visited = set()

        for node in range(V):
            if node not in visited:
                if self.dfs_cycle_detection(graph, visited, node, -1):
                    return True

        return False

    def dfs_cycle_detection(self, graph, visited, curNode, parentNode):
        visited.add(curNode)

        for neighbor in graph[curNode]:
            if neighbor == parentNode:
                continue

            if neighbor in visited:
                return True

            if self.dfs_cycle_detection(graph, visited, neighbor, curNode):
                return True

        return False

BFS

Interactive Visualization

Python

from collections import defaultdict, deque


class Solution:
    def isCycle(self, V, edges):
        graph = defaultdict(list)
        for src, dst in edges:
            graph[src].append(dst)
            graph[dst].append(src)

        visited = set()

        for node in range(V):
            if node not in visited:
                if self.bfs_cycle_detection(graph, visited, node):
                    return True

        return False

    def bfs_cycle_detection(self, graph, visited, start):
        queue = deque([(start, -1)])
        visited.add(start)

        while queue:
            current, parent = queue.popleft()

            for neighbor in graph[current]:
                if neighbor == parent:
                    continue

                if neighbor in visited:
                    return True

                visited.add(neighbor)
                queue.append((neighbor, current))

        return False

---

Cycle Detection in Directed Graph

In a directed graph, a cycle is a path that starts and ends at the same node following edge directions. The most common and effective method is using Depth-First Search (DFS) with a recursion stack.

Approach - DFS and BFS

• DFS: We make use of a visited set and current path set to detect a cycle. In a directed graph, we need to keep track of the current path because not all revists are cycles. We need to distinguish between

  • Revisiting a node that is still being processed (i.e., we're currently exploring it in a recursion path)
  • Revisiting a node that is already fully processed (i.e., the path from the node has been fully explored with no cycles)

• BFS: We make use of Kahn's Algorithm which is a BFS-based technique used for topological sorting of a directed acyclic graph (DAG). It works by repeatedly removing nodes with in-degree 0 and reducing the in-degree of their neighbours. If all nodes are processed, the graph has no cycle. If some nodes remain (i.e. non-zero in-degree), a cycle exists. It’s commonly used for cycle detection and task scheduling problems.

Directed Graph Cycle

Medium2

207. Course ScheduleMedium

210. Course Schedule IIMedium

Directed Graph Cycle

DFS

Interactive Visualization

Python

from collections import defaultdict


class Solution:
    def isCycle(self, V, edges):
        graph = defaultdict(list)
        for src, dst in edges:
            graph[src].append(dst)

        visited = set()
        for node in range(V):
            if node not in visited and self.dfs_cycle_detection(
                graph, node, visited, set()
            ):
                return True

        return False

    def dfs_cycle_detection(self, graph, curNode, visited, curPath):
        if curNode in curPath:
            return True

        if curNode in visited:
            return False

        visited.add(curNode)
        curPath.add(curNode)

        for neighbor in graph[curNode]:
            if self.dfs_cycle_detection(graph, neighbor, visited, curPath):
                return True

        curPath.remove(curNode)
        return False

BFS - Khan's algorithm

Interactive Visualization

Python

from collections import defaultdict, deque


class Solution:
    def isCycle(self, V, edges):
        graph = defaultdict(list)
        in_degree = [0] * V

        for src, dst in edges:
            graph[src].append(dst)
            in_degree[dst] += 1

        queue = deque()
        for node in range(V):
            if in_degree[node] == 0:
                queue.append(node)

        processed_count = 0

        while queue:
            current = queue.popleft()
            processed_count += 1

            for neighbor in graph[current]:
                in_degree[neighbor] -= 1
                if in_degree[neighbor] == 0:
                    queue.append(neighbor)

        return processed_count != V

---