Detect Cycles in a Directed Graph using DFS

During the DFS traversal, we can keep track of the visited nodes and the current path. If we encounter a node that has already been visited and is still on the current path, then we have detected a cycle.

function isCyclic(adj:number[][], v:number){
  let helper:boolean[] = new Array<boolean>(v).fill(false);
  let visited:boolean[] = new Array<boolean>(v).fill(false);
  for(let i:number=0 ; i<v;i++){
    console.log(visited);
    if(visited[i] == false ){
      //call DFS
      const ans = DFS(adj, i, helper, visited);
      if(ans==true) return true;
    }
  }
  return false;

}

function DFS(adj:number[][], index:number,helper:boolean[], visited:boolean[]){
  helper[index] = true;
  visited[index] = true;
  let neighbor = adj[index];
  for(let k:number =0 ; k<neighbor.length;k++){
    let curr = neighbor[k];
    if(helper[curr]==true) return true;
    if(visited[curr]==false){
      let ans = DFS(adj,curr, helper, visited);
      if(ans == true) return true;
    }
  }
  helper[index] = false;
  return false;
}

const matrix:number[][] = [[0,1],[1,2],[2,3],[3,4],[4,4]]
console.log(isCyclic(matrix, matrix.length))

This code is implementing a solution to detect cycles in a directed graph using Depth First Search (DFS) algorithm.

The isCyclic function takes an adjacency matrix and the number of vertices as inputs. It initializes two arrays: helper to keep track of nodes on the current path and visited to keep track of visited nodes. It then loops through each unvisited node and calls the DFS function on it. If the DFS function returns true, indicating that a cycle is found, the isCyclic function returns true. Otherwise, it continues to the next unvisited node.

The DFS function takes the adjacency matrix, the index of the current node, and the helper and visited arrays as inputs. It first marks the current node as visited and adds it to the helper array to keep track of nodes on the current path. It then loops through each neighbor of the current node and recursively calls itself on unvisited neighbors. If it encounters a neighbor that is already on the helper array, it returns true to indicate the presence of a cycle. Otherwise, it continues to the next neighbor. After exploring all neighbors, the function removes the current node from the helper array and returns false.

The code seems to be correct and will work for detecting cycles in a directed graph represented by an adjacency matrix. However, note that this implementation assumes that the graph is a simple directed graph with no self-loops. If the graph has self-loops or multiple edges between nodes, the implementation may need to be modified.