Detect Cycles in a Graph

A cycle in a graph is a sequence of edges and vertices where you can start from a specific vertex, follow a continuous path, and return to the same vertex without repeating any edge. In simpler terms, a cycle occurs when you can start at a vertex, traverse a set of edges, and return to the same vertex without retracing any edge.

Detecting cycles in a graph is crucial for several reasons. It helps identify potential problems like deadlocks in operating systems, ensures the reliability of dependency management in software development, and prevents infinite loops in network routing protocols.

Various algorithms have been developed to detect cycles in a graph, each with different approaches and efficiencies. Depth-First Search (DFS) is a common method that uses a recursive approach to explore all possible paths from a vertex and backtracks upon revisiting any vertex, thereby identifying cycles. Another popular algorithm is the Union-Find algorithm, which is effective in detecting cycles in undirected graphs by maintaining a disjoint-set data structure.

In this article we will look at DFS based algorithms to detect cycles in directed and un-directed graphs.

Detect Cycles in an Undirected Graph

Here’s the algorithm to detect cycles in an undirected graph:

Perform a depth-first search (DFS) traversal starting from each unvisited vertex
During DFS traversal, mark current vertex as visited
For each unvisited neighbor from the current vertex:
- If the neighbor vertex is not visited, perform DFS on this vertex
- If the neighbor vertex is already visited, it means there is a cycle

Below is the implementation:


def dfs(vertex, graph, visited, parent):
  """
  Perform a depth-first search to detect cycles in un-directed graph,
  starting from a given node
  
  Arguments:
  vertex: the current vertex being visited
  graph: the adjacency list representing the directed graph
  visited: set of visited nodes
  parent: the parent of the current node

  Returns:
  True if a cycle is detected, otherwise False.
  """
  
  # Mark the current node as visited
  visited.add(vertex)

  # Traverse through all the neighbors of the current node
  for neighbor in graph[vertex]:
    # If the neighbor is not visited yet
    if neighbor not in visited:
      # Recursively call DFS on the neighbor
      if dfs(neighbor, graph, visited, vertex):
        return True
    # If the neighbor is visited and not the parent of the current node
    elif neighbor != parent:
      # There is a cycle detected
      return True

  # No cycle detected for the current node
  return False

def detect_cycle(graph):
  """
  Function to detect if there is a cycle in the graph

  Arguments:
  graph: the adjacency list representing the undirected graph

  Returns:
  True if a cycle is detected, otherwise False.
  """
  # Initialize a set to keep track of visited nodes
  visited = set()

  # Traverse through all the nodes in the graph
  for node in graph:
    # If the node is not visited yet
    if node not in visited:
      # Call the DFS function on the node
      if dfs(node, graph, visited, None):
        return True

  # No cycle detected in the graph
  return False

# Sample graph to test cycle detection
graph1 = {
    'A' : ['B', 'C'],
    'B' : ['A', 'C', 'D'],
    'C' : ['A', 'B', 'E', 'F'],
    'D' : ['B'],
    'E' : ['C'],
    'F' : ['C']
}

if detect_cycle(graph1):
  print("Graph 1 has a cycle!")
else:
  print("Graph 1 does not has a cycle!")

# Sample graph to test cycle detection
graph2 = {
    'A' : ['B', 'C'],
    'B' : ['A', 'D'],
    'C' : ['A', 'E', 'F'],
    'D' : ['B'],
    'E' : ['C'],
    'F' : ['C']
}

if detect_cycle(graph2):
  print("Graph 2 has a cycle!")
else:
  print("Graph 2 does not has a cycle!")


#include <iostream>
#include <unordered_set>
#include <vector>

using namespace std;

// Function to perform depth-first search to detect cycles in an undirected graph
bool dfs(int vertex, vector<vector<pair<int, int>>>& graph, unordered_set<int>& visited, int parent) {
  // Mark the current node as visited
  visited.insert(vertex);

  // Traverse through all the neighbors of the current node
  for (const auto& neighbor : graph[vertex]) {
    // If the neighbor is not visited yet
    if (visited.find(neighbor.first) == visited.end()) {
      // Recursively call DFS on the neighbor
      if (dfs(neighbor.first, graph, visited, vertex)) {
        return true;
      }
    }
    // If the neighbor is visited and not the parent of the current node
    else if (neighbor.first != parent) {
      // There is a cycle detected
      return true;
    }
  }

  // No cycle detected for the current node
  return false;
}

// Function to detect if there is a cycle in the graph
bool detect_cycle(vector<vector<pair<int, int>>>& graph) {
  // Initialize a set to keep track of visited nodes
  unordered_set<int> visited;

  // Traverse through all the nodes in the graph
  for (int node = 0; node < graph.size(); node++) {
    // If the node is not visited yet
    if (visited.find(node) == visited.end()) {
      // Call the DFS function on the node
      if (dfs(node, graph, visited, -1)) {
        return true;
      }
    }
  }

  // No cycle detected in the graph
  return false;
}

int main() {
  // Sample graph to test cycle detection
  vector<vector<pair<int, int>>> graph1 = {
      {{1, 0}, {2, 0}},
      {{0, 0}, {2, 0}, {3, 0}},
      {{0, 0}, {1, 0}, {4, 0}, {5, 0}},
      {{1, 0}},
      {{2, 0}},
      {{2, 0}}
  };

  if (detect_cycle(graph1)) {
    cout << "Graph 1 has a cycle!" << endl;
  } else {
    cout << "Graph 1 does not have a cycle!" << endl;
  }

  // Sample graph to test cycle detection
  vector<vector<pair<int, int>>> graph2 = {
      {{1, 0}, {2, 0}},
      {{0, 0}, {3, 0}},
      {{0, 0}, {4, 0}, {5, 0}},
      {{1, 0}},
      {{2, 0}},
      {{2, 0}}
  };

  if (detect_cycle(graph2)) {
    cout << "Graph 2 has a cycle!" << endl;
  } else {
    cout << "Graph 2 does not have a cycle!" << endl;
  }

  return 0;
}


// Function to perform depth-first search to detect cycles in an undirected graph
function dfs(vertex, graph, visited, parent) {
  // Mark the current node as visited
  visited.add(vertex);

  // Traverse through all the neighbors of the current node
  for (let neighbor of graph[vertex]) {
    // If the neighbor is not visited yet
    if (!visited.has(neighbor)) {
      // Recursively call DFS on the neighbor
      if (dfs(neighbor, graph, visited, vertex)) {
        return true;
      }
    }
    // If the neighbor is visited and not the parent of the current node
    else if (neighbor !== parent) {
      // There is a cycle detected
      return true;
    }
  }

  // No cycle detected for the current node
  return false;
}

// Function to detect if there is a cycle in the graph
function detectCycle(graph) {
  // Initialize a set to keep track of visited nodes
  const visited = new Set();

  // Traverse through all the nodes in the graph
  for (let node in graph) {
    // If the node is not visited yet
    if (!visited.has(node)) {
      // Call the DFS function on the node
      if (dfs(node, graph, visited, null)) {
        return true;
      }
    }
  }

  // No cycle detected in the graph
  return false;
}

// Sample graph to test cycle detection
const graph1 = {
  'A': ['B', 'C'],
  'B': ['A', 'C', 'D'],
  'C': ['A', 'B', 'E', 'F'],
  'D': ['B'],
  'E': ['C'],
  'F': ['C']
};

if (detectCycle(graph1)) {
  console.log("Graph 1 has a cycle!");
} else {
  console.log("Graph 1 does not have a cycle!");
}

// Sample graph to test cycle detection
const graph2 = {
  'A': ['B', 'C'],
  'B': ['A', 'D'],
  'C': ['A', 'E', 'F'],
  'D': ['B'],
  'E': ['C'],
  'F': ['C']
};

if (detectCycle(graph2)) {
  console.log("Graph 2 has a cycle!");
} else {
  console.log("Graph 2 does not have a cycle!");
}


import java.util.*;

public class Main {
  // Perform a depth-first search to detect cycles in an undirected graph,
  // starting from a given node
  public static boolean dfs(String vertex, Map<String, List<String>> graph, Set<String> visited, String parent) {
    // Mark the current node as visited
    visited.add(vertex);

    // Traverse through all the neighbors of the current node
    for (String neighbor : graph.get(vertex)) {
      // If the neighbor is not visited yet
      if (!visited.contains(neighbor)) {
        // Recursively call DFS on the neighbor
        if (dfs(neighbor, graph, visited, vertex)) {
          return true;
        }
      }
      // If the neighbor is visited and not the parent of the current node
      else if (!neighbor.equals(parent)) {
        // There is a cycle detected
        return true;
      }
    }

    // No cycle detected for the current node
    return false;
  }

  // Function to detect if there is a cycle in the graph
  public static boolean detectCycle(Map<String, List<String>> graph) {
    // Initialize a set to keep track of visited nodes
    Set<String> visited = new HashSet<>();

    // Traverse through all the nodes in the graph
    for (String node : graph.keySet()) {
      // If the node is not visited yet
      if (!visited.contains(node)) {
        // Call the DFS function on the node
        if (dfs(node, graph, visited, null)) {
          return true;
        }
      }
    }

    // No cycle detected in the graph
    return false;
  }

  public static void main(String[] args) {
    // Sample graph to test cycle detection
    Map<String, List<String>> graph1 = new HashMap<>();
    graph1.put("A", new ArrayList<>(Arrays.asList("B", "C")));
    graph1.put("B", new ArrayList<>(Arrays.asList("A", "C", "D")));
    graph1.put("C", new ArrayList<>(Arrays.asList("A", "B", "E", "F")));
    graph1.put("D", new ArrayList<>(Arrays.asList("B")));
    graph1.put("E", new ArrayList<>(Arrays.asList("C")));
    graph1.put("F", new ArrayList<>(Arrays.asList("C")));

    if (detectCycle(graph1)) {
      System.out.println("Graph 1 has a cycle!");
    } else {
      System.out.println("Graph 1 does not have a cycle!");
    }

    // Sample graph to test cycle detection
    Map<String, List<String>> graph2 = new HashMap<>();
    graph2.put("A", new ArrayList<>(Arrays.asList("B", "C")));
    graph2.put("B", new ArrayList<>(Arrays.asList("A", "D")));
    graph2.put("C", new ArrayList<>(Arrays.asList("A", "E", "F")));
    graph2.put("D", new ArrayList<>(Arrays.asList("B")));
    graph2.put("E", new ArrayList<>(Arrays.asList("C")));
    graph2.put("F", new ArrayList<>(Arrays.asList("C")));

    if (detectCycle(graph2)) {
      System.out.println("Graph 2 has a cycle!");
    } else {
      System.out.println("Graph 2 does not have a cycle!");
    }
  }
}

Detect Cycles in an directed Graph

Here’s an algorithm to detect cycles in a directed graph using the white, gray, and black (0, 1, 2) marking technique:

Initialize all vertices in the graph as white (0).
Perform a depth-first search (DFS) traversal starting from vertices still marked as white.
During the DFS traversal, mark each vertex as follows:
- When a vertex is first visited, mark it as gray (1).
- When the DFS has finished exploring all the vertices reachable from the current vertex, mark it as black (2).
If, during the DFS traversal, a gray vertex is encountered, it means a cycle has been detected.

Below is the implementation:


WHITE = 0
GRAY = 1
BLACK = 2

def dfs(vertex, graph, color_of_vertex):
  """
  Perform a depth-first search to detect cycles in directed graph,
  starting from a given vertex
  
  Arguments:
  vertex: the current vertex being visited
  graph: the adjacency list representing the directed graph
  color_of_vertex: dictonary containing the color of each vertex

  Returns:
  True if a cycle is detected, otherwise False.
  """

  # Mark the current vertex as gray (in progress)
  color_of_vertex[vertex] = GRAY

  # Check all neighboring vertices
  for neighbor in graph[vertex]:
    if color_of_vertex[neighbor] == WHITE:
      # If the neighbor hasn't been visited, explore it
      if dfs(neighbor, graph, color_of_vertex) == True:
        return True  # Cycle detected in subtree
    elif color_of_vertex[neighbor] == GRAY:
      # If we find a gray neighbor, we've found a cycle
      return True

  # Mark the vertex as black
  # This means that all vertices reachable from this node
  # are fully explored before backtracking
  color_of_vertex[vertex] = BLACK
  
  # No cycle found in this subtree
  return False

def detect_cycle(graph):
  # Initialize all vertices as white (not visited)
  color_of_vertex = {}
  for vertex in graph:
    color_of_vertex[vertex] = WHITE

  # Check each vertex in the graph
  for vertex in graph:
    # If the vertex hasn't been visited, start a DFS
    if color_of_vertex[vertex] == WHITE:
      if dfs(vertex, graph, color_of_vertex) == True:
        return True  # Cycle detected

  # If we've checked all vertices and found no cycles
  return False


# Sample graph to test cycle detection
graph1 = {
  'A' : ['C'],
  'B' : ['A', 'D'],
  'C' : ['B', 'D'],
  'D' : [],
}

if detect_cycle(graph1):
  print("Graph 1 has a cycle!")
else:
  print("Graph 1 does not has a cycle!")

# Sample graph to test cycle detection
graph2 = {
  'A' : ['B', 'C'],
  'B' : ['D'],
  'C' : ['B', 'D'],
  'D' : [],
}


if detect_cycle(graph2):
  print("Graph 2 has a cycle!")
else:
  print("Graph 2 does not has a cycle!")


#include <iostream>
#include <unordered_map>
#include <vector>

const int WHITE = 0;
const int GRAY = 1;
const int BLACK = 2;

bool dfs(std::string vertex, std::unordered_map<std::string, std::vector<std::string>>& graph, std::unordered_map<std::string, int>& color_of_vertex) {
  // Mark the current vertex as gray (in progress)
  color_of_vertex[vertex] = GRAY;

  // Check all neighboring vertices
  for (const auto& neighbor : graph[vertex]) {
    if (color_of_vertex[neighbor] == WHITE) {
      // If the neighbor hasn't been visited, explore it
      if (dfs(neighbor, graph, color_of_vertex)) {
        return true;  // Cycle detected in subtree
      }
    } else if (color_of_vertex[neighbor] == GRAY) {
      // If we find a gray neighbor, we've found a cycle
      return true;
    }
  }

  // Mark the vertex as black
  // This means that all vertices reachable from this node
  // are fully explored before backtracking
  color_of_vertex[vertex] = BLACK;

  // No cycle found in this subtree
  return false;
}

bool detect_cycle(std::unordered_map<std::string, std::vector<std::string>>& graph) {
  // Initialize all vertices as white (not visited)
  std::unordered_map<std::string, int> color_of_vertex;
  for (const auto& pair : graph) {
    color_of_vertex[pair.first] = WHITE;
  }

  // Check each vertex in the graph
  for (const auto& pair : graph) {
    // If the vertex hasn't been visited, start a DFS
    if (color_of_vertex[pair.first] == WHITE) {
      if (dfs(pair.first, graph, color_of_vertex)) {
        return true;  // Cycle detected
      }
    }
  }

  // If we've checked all vertices and found no cycles
  return false;
}

int main() {
  // Sample graph to test cycle detection
  std::unordered_map<std::string, std::vector<std::string>> graph1 = {
    {"A", {"C"}},
    {"B", {"A", "D"}},
    {"C", {"B", "D"}},
    {"D", {}}
  };

  if (detect_cycle(graph1)) {
    std::cout << "Graph 1 has a cycle!" << std::endl;
  } else {
    std::cout << "Graph 1 does not have a cycle!" << std::endl;
  }

  // Sample graph to test cycle detection
  std::unordered_map<std::string, std::vector<std::string>> graph2 = {
    {"A", {"B", "C"}},
    {"B", {"D"}},
    {"C", {"B", "D"}},
    {"D", {}}
  };

  if (detect_cycle(graph2)) {
    std::cout << "Graph 2 has a cycle!" << std::endl;
  } else {
    std::cout << "Graph 2 does not have a cycle!" << std::endl;
  }

  return 0;
}


const WHITE = 0;
const GRAY = 1;
const BLACK = 2;

function dfs(vertex, graph, colorOfVertex) {
  // Mark the current vertex as gray (in progress)
  colorOfVertex[vertex] = GRAY;

  // Check all neighboring vertices
  for (const neighbor of graph[vertex]) {
    if (colorOfVertex[neighbor] === WHITE) {
      // If the neighbor hasn't been visited, explore it
      if (dfs(neighbor, graph, colorOfVertex) === true) {
        return true; // Cycle detected in subtree
      }
    } else if (colorOfVertex[neighbor] === GRAY) {
      // If we find a gray neighbor, we've found a cycle
      return true;
    }
  }

  // Mark the vertex as black
  // This means that all vertices reachable from this node
  // are fully explored before backtracking
  colorOfVertex[vertex] = BLACK;

  // No cycle found in this subtree
  return false;
}

function detectCycle(graph) {
  // Initialize all vertices as white (not visited)
  const colorOfVertex = {};
  for (const vertex in graph) {
    colorOfVertex[vertex] = WHITE;
  }

  // Check each vertex in the graph
  for (const vertex in graph) {
    // If the vertex hasn't been visited, start a DFS
    if (colorOfVertex[vertex] === WHITE) {
      if (dfs(vertex, graph, colorOfVertex) === true) {
        return true; // Cycle detected
      }
    }
  }

  // If we've checked all vertices and found no cycles
  return false;
}

// Sample graph to test cycle detection
const graph1 = {
  A: ['C'],
  B: ['A', 'D'],
  C: ['B', 'D'],
  D: [],
};

if (detectCycle(graph1)) {
  console.log('Graph 1 has a cycle!');
} else {
  console.log('Graph 1 does not have a cycle!');
}

// Sample graph to test cycle detection
const graph2 = {
  A: ['B', 'C'],
  B: ['D'],
  C: ['B', 'D'],
  D: [],
};

if (detectCycle(graph2)) {
  console.log('Graph 2 has a cycle!');
} else {
  console.log('Graph 2 does not have a cycle!');
}


import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;

public class Main {
  private static final int WHITE = 0;
  private static final int GRAY = 1;
  private static final int BLACK = 2;

  public static boolean dfs(String vertex, HashMap<String, List<String>> graph, HashMap<String, Integer> colorOfVertex) {
    /**
     * Perform a depth-first search to detect cycles in directed graph,
     * starting from a given vertex
     * 
     * Arguments:
     * vertex: the current vertex being visited
     * graph: the adjacency list representing the directed graph
     * colorOfVertex: dictionary containing the color of each vertex
     * 
     * Returns:
     * True if a cycle is detected, otherwise False.
     */

    // Mark the current vertex as gray (in progress)
    colorOfVertex.put(vertex, GRAY);

    // Check all neighboring vertices
    for (String neighbor : graph.get(vertex)) {
      if (colorOfVertex.get(neighbor) == WHITE) {
        // If the neighbor hasn't been visited, explore it
        if (dfs(neighbor, graph, colorOfVertex)) {
          return true; // Cycle detected in subtree
        }
      } else if (colorOfVertex.get(neighbor) == GRAY) {
        // If we find a gray neighbor, we've found a cycle
        return true;
      }
    }

    // Mark the vertex as black
    // This means that all vertices reachable from this node
    // are fully explored before backtracking
    colorOfVertex.put(vertex, BLACK);

    // No cycle found in this subtree
    return false;
  }

  public static boolean detectCycle(HashMap<String, List<String>> graph) {
    // Initialize all vertices as white (not visited)
    HashMap<String, Integer> colorOfVertex = new HashMap<>();
    for (String vertex : graph.keySet()) {
      colorOfVertex.put(vertex, WHITE);
    }

    // Check each vertex in the graph
    for (String vertex : graph.keySet()) {
      // If the vertex hasn't been visited, start a DFS
      if (colorOfVertex.get(vertex) == WHITE) {
        if (dfs(vertex, graph, colorOfVertex)) {
          return true; // Cycle detected
        }
      }
    }

    // If we've checked all vertices and found no cycles
    return false;
  }

  public static void main(String[] args) {
    // Sample graph to test cycle detection
    HashMap<String, List<String>> graph1 = new HashMap<>();
    graph1.put("A", new ArrayList<>() {{ add("C"); }});
    graph1.put("B", new ArrayList<>() {{ add("A"); add("D"); }});
    graph1.put("C", new ArrayList<>() {{ add("B"); add("D"); }});
    graph1.put("D", new ArrayList<>());

    if (detectCycle(graph1)) {
      System.out.println("Graph 1 has a cycle!");
    } else {
      System.out.println("Graph 1 does not has a cycle!");
    }

    // Sample graph to test cycle detection
    HashMap<String, List<String>> graph2 = new HashMap<>();
    graph2.put("A", new ArrayList<>() {{ add("B"); add("C"); }});
    graph2.put("B", new ArrayList<>() {{ add("D"); }});
    graph2.put("C", new ArrayList<>() {{ add("B"); add("D"); }});
    graph2.put("D", new ArrayList<>());

    if (detectCycle(graph2)) {
      System.out.println("Graph 2 has a cycle!");
    } else {
      System.out.println("Graph 2 does not has a cycle!");
    }
  }
}