Cycle Detection in Directed Graph in DSA Typescript - Build from Scratch

Cycle Detection in Directed Graph

📖 Scenario: Imagine you are building a task scheduler that runs tasks in order. Each task can depend on other tasks. To make sure the scheduler works correctly, you need to check if there is a cycle in the task dependencies. A cycle means some tasks depend on each other in a loop, which makes scheduling impossible.

🎯 Goal: You will create a program that detects if there is a cycle in a directed graph representing task dependencies. The graph is given as an adjacency list. You will use depth-first search (DFS) with recursion to find cycles.

📋 What You'll Learn

Create a directed graph as an adjacency list using a TypeScript object.

Create a helper array to track visited nodes and recursion stack.

Implement a recursive function to detect cycles using DFS.

Print whether the graph contains a cycle or not.

💡 Why This Matters

🌍 Real World

Cycle detection is important in task scheduling, detecting deadlocks, and verifying dependencies in software projects.

💼 Career

Understanding cycle detection helps in roles like software developer, system engineer, and data scientist where graph algorithms are used.

1

Create the directed graph as an adjacency list

Create a variable called graph as an object with these exact entries: 0: [1], 1: [2], 2: [0, 3], 3: [4], 4: []

DSA Typescript

# Your code here

Hint

Use a TypeScript object where keys are numbers and values are arrays of numbers representing edges.

2

Create visited and recursion stack arrays

Create two boolean arrays called visited and recStack with length 5, initialized with false values

DSA Typescript

const graph: { [key: number]: number[] } = {
  0: [1],
  1: [2],
  2: [0, 3],
  3: [4],
  4: []
};
// Your code here

Hint

Use new Array(5).fill(false) to create arrays of booleans.

3

Implement the recursive DFS function to detect cycles

Write a function called isCyclicUtil that takes a node number and returns a boolean. It should mark visited[node] and recStack[node] as true. Then for each neighbor in graph[node], if the neighbor is not visited, recursively call isCyclicUtil(neighbor) and return true if it returns true. If the neighbor is in recStack, return true. After checking neighbors, set recStack[node] to false and return false.

DSA Typescript

const graph: { [key: number]: number[] } = {
  0: [1],
  1: [2],
  2: [0, 3],
  3: [4],
  4: []
};

const visited: boolean[] = new Array(5).fill(false);
const recStack: boolean[] = new Array(5).fill(false);

// Your code here

Hint

Use recursion and check neighbors carefully. Remember to update recStack when entering and leaving nodes.

4

Check all nodes and print if the graph has a cycle

Write a loop from 0 to 4 using i. For each i, if visited[i] is false, call isCyclicUtil(i). If it returns true, print "Graph contains a cycle" and return. After the loop, print "Graph does not contain a cycle".

DSA Typescript

const graph: { [key: number]: number[] } = {
  0: [1],
  1: [2],
  2: [0, 3],
  3: [4],
  4: []
};

const visited: boolean[] = new Array(5).fill(false);
const recStack: boolean[] = new Array(5).fill(false);

function isCyclicUtil(node: number): boolean {
  visited[node] = true;
  recStack[node] = true;

  for (const neighbor of graph[node]) {
    if (!visited[neighbor]) {
      if (isCyclicUtil(neighbor)) {
        return true;
      }
    } else if (recStack[neighbor]) {
      return true;
    }
  }

  recStack[node] = false;
  return false;
}

// Your code here

Hint

Loop through all nodes and call isCyclicUtil. Print the result based on the return value.