Cycle In Graph

Tags

Cycle In Graph

Category

Graphs

Difficulty

Medium

Problem Statement

Given a directed graph represented as an adjacency list (where the index represents a node and the value at that index is a list of nodes it has edges to), determine whether the graph contains a cycle.

Intuition

A cycle in a directed graph exists when a DFS traversal encounters a node that is currently on the recursion stack (i.e., part of the current exploration path). We use a coloring scheme with three states:

  • White (unvisited): not yet explored.
  • Gray (in stack): currently being explored (on the current DFS path).
  • Black (done): fully explored with all descendants processed.

If during DFS we encounter a gray node, we have found a back edge, which means a cycle exists.

Approach

  1. Initialize all nodes as WHITE.
  2. For each unvisited node, start a DFS.
  3. During DFS on a node: a. Mark it as GRAY (currently exploring). b. For each neighbor:
    • If GRAY: cycle detected, return true.
    • If WHITE: recursively DFS on it; if it returns true, propagate true. c. Mark the node as BLACK (fully explored). d. Return false.
  4. If no cycle is found after processing all nodes, return false.

Pseudocode

WHITE = 0, GRAY = 1, BLACK = 2

function cycleInGraph(edges):
    n = length(edges)
    colors = array of n, all WHITE

    for node from 0 to n - 1:
        if colors[node] == WHITE:
            if dfs(node, edges, colors):
                return true
    return false

function dfs(node, edges, colors):
    colors[node] = GRAY
    for neighbor in edges[node]:
        if colors[neighbor] == GRAY:
            return true
        if colors[neighbor] == WHITE:
            if dfs(neighbor, edges, colors):
                return true
    colors[node] = BLACK
    return false

Time & Space Complexity

  • Time: O(V + E), where V is the number of vertices and E is the number of edges. Each node and edge is processed once.
  • Space: O(V) for the color array and recursion stack.

Key Insights

  • The three-color scheme distinguishes between "currently on the path" (gray) and "already fully explored" (black). This distinction is critical for directed graphs because visiting an already-explored node is not a cycle (unlike undirected graphs).
  • In an undirected graph, detecting a visited non-parent node is sufficient for cycle detection. In a directed graph, only back edges (to gray nodes) indicate cycles.
  • Self-loops (a node with an edge to itself) are immediately detected since the node is gray when its neighbors are checked.
  • Topological sort is possible if and only if no cycle exists.

Edge Cases

  • Graph with no edges: no cycle.
  • Self-loop on any node: cycle exists.
  • Two nodes pointing to each other: cycle exists.
  • Disconnected graph: must check all components.
  • Single node with no edges: no cycle.
  • DAG (directed acyclic graph): should correctly return false.

Linked mentions