Cycle detection

Introduction

A cycle occurs in a graph when a duplicate node is encountered when traversing a tree using a depth first search. In other words, a cycle occurs when you can reach the same node through a path in a graph.

An undirected graph where the number of edges is greater than or equal to the number of nodes will always have cycles.

Implementation

We first mark every node as unvisited. We start at each unvisited node and we do a depth first search from that node. We mark each node along the way as temporarily visited and if we encounter a temporarily visited node, then we have a cycle. After temporarily visiting the nodes, we mark them as visited. If we reach a visited node again, then we stop since we already checked if that node had a cycle.

public static boolean hasCycle(int[][] adjMatrix) {
  int[] visited = new int[adjMatrix.length];
  
  // Mark each node as unvisited.
  for (int i = 0; i < adjMatrix.length; i++) {
    visited[i] = 0;
  }
  // Check if current node leads to a cycle.
  for (int i = 0; i < adjMatrix.length; i++) {
    if (hasCycleAt(adjMatrix, i, visited)) {
      return true;
    }
  }
  return false;
}

public static boolean hasCycleAt(int[][] adjMatrix, int i, int visited[]) {
  // If node has been reached again from the starting node, we have a cycle.
  if (visited[i] == 1) {
    return true;
  }
  // If node has been permanently visited, we know it was already checked.
  if(visited[i] == 2) {
    return false;
  }
  
  // Mark node as temporarily visited.
  visited[i] = 1;
  
  // Iterate through neighbors of current node.
  for (int j = 0; j < adjMatrix.length; i++) {
    if (adjMatrix[i][j] > 0) {
      // Recursively check is 
      if (hasCycleAt(adjMatrix, j, visited)) {
        return true;
      }
      visited[j] = 0;
    }
  }
  // Permanently mark node as visited.
  visited[i] = 2;
  return false;
}