Detect a Cycle in a Graph

Detect a Cycle in a Graph

January 4, 2024
medium
DFS, graph

Problem #

Given a directed graph, write a function to detect whether the graph contains a cycle.

Example: Input: Graph with edges [[0, 1], [1, 2], [2, 0]] Output: True (There is a cycle 0 -> 1 -> 2 -> 0)

Solution #

  • Algorithm: Depth-First Search (DFS) Use DFS to detect the presence of a cycle in the graph. The idea is to traverse the graph along a particular path and if during the traversal we revisit a node, then there is a cycle in the graph.

Algorithm Steps: #

  1. Create an Adjacency List: Represent the graph using an adjacency list for efficient traversal.
  2. DFS with Recursion Stack: Use DFS to traverse the graph. Keep track of the nodes currently in the recursion stack.
  3. Check for Cycles: If a node is visited again and is in the current recursion stack, a cycle is detected.
  4. Explore All Nodes: Ensure all nodes are explored since the graph might be disconnected.

  • Python Code:

    def isCyclic(graph):
    def dfs(vertex, visited, recStack):
        visited[vertex] = True
        recStack[vertex] = True

        for neighbour in graph[vertex]:
            if not visited[neighbour]:
                if dfs(neighbour, visited, recStack):
                    return True
            elif recStack[neighbour]:
                return True

        recStack[vertex] = False
        return False

    visited = [False] * len(graph)
    recStack = [False] * len(graph)
    for node in range(len(graph)):
        if not visited[node]:
            if dfs(node, visited, recStack):
                return True
    return False

# Example Usage
graph = {0: [1], 1: [2], 2: [0]}
print(isCyclic(graph))

  • Explanation:

    • Create two boolean arrays visited and recStack.
    • Use DFS to traverse the graph.
    • If an unvisited node leads to a node already in the recursion stack, a cycle exists.
    • Return True if a cycle is found, otherwise False.

Time Complexity: #

  • O(V + E): Where V is the number of vertices and E is the number of edges. The DFS traversal takes O(V + E) time.

Space Complexity: #

  • O(V): The space is used for the visited and recursion stack arrays.

This problem is fundamental in graph theory and algorithms, and understanding how to detect cycles in directed graphs is crucial for many applications, making it a suitable question for technical interviews at companies like Google, Amazon, Meta, and OpenAI.