Directed Graph - Detect Cycle

solution.ts

export function cycleInGraph(edges: number[][]) {

  // 1. loop through all vertices of the graph 
  for (let v = 0; v < edges.length; v++) {
    if (hasCycle(edges, v, new Set<Number>()))
      return true;
  }

  return false;
}

/**
 * Checks whether there is a cycle for the given vertex
 * Implements DFS approach for iterating over the adj vertices
 * @param adjList Adjacency list or Graph
 * @param v The current vertex
 * @param visited Visited stack
 * @returns 
 */
function hasCycle(adjList: number[][], v: number, visited: Set<Number>): boolean {
  
  // 4. if the current vertex was visited earlier in the stack then it means that
  // there is a cycle
  if(visited.has(v)) return true;
  // 3. Think of the visited set as a current stack where we add the 
  // current vertex in the set before begining DFS over it 
  else visited.add(v);

  // 2. loop through all adjacent vertices of the current vertex
  for(let adjV of adjList[v]) {
    if(hasCycle(adjList, adjV, visited)) {
      return true;
    }
  }

  // 5. remove the current vertex from the stack 
  visited.delete(v);
  return false;
}