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

Cycle Detection in Undirected Graph

📖 Scenario: Imagine you are working on a network of friends where each friend is connected to others. You want to check if there is any circle of friends where you can start from one friend and come back to the same friend by following connections without repeating edges.

🎯 Goal: You will build a program to detect if there is a cycle in an undirected graph using adjacency lists and depth-first search.

📋 What You'll Learn

Create an adjacency list to represent the graph

Use a helper array to track visited nodes

Implement a depth-first search function to detect cycles

Print true if a cycle exists, otherwise false

💡 Why This Matters

🌍 Real World

Cycle detection helps find loops in networks like social connections, computer networks, or road maps to avoid repeated paths or errors.

💼 Career

Understanding cycle detection is important for software engineers working on graph algorithms, network analysis, and debugging complex data structures.

1

Create the graph adjacency list

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

DSA Typescript

# Your code here

Hint

Use an object where keys are node numbers and values are arrays of connected nodes.

2

Create a visited array

Create a variable called visited as an array of booleans with length 4, initialized with false values

DSA Typescript

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

Hint

Use an array with four false values to mark nodes as not visited yet.

3

Implement DFS function to detect cycle

Write a function called dfs that takes node and parent as parameters. Inside, mark visited[node] as true. Then loop over neighbors in graph[node]. If a neighbor is not visited, recursively call dfs with neighbor and current node. If a neighbor is visited and not equal to parent, return true. Return false if no cycle found.

DSA Typescript

const graph: { [key: number]: number[] } = {
  0: [1, 2],
  1: [0, 2],
  2: [0, 1, 3],
  3: [2]
};
const visited: boolean[] = [false, false, false, false];
// Write dfs function here
# Your code here

Hint

Use recursion to visit neighbors and check if a visited neighbor is not the parent to detect a cycle.

4

Check for cycle and print result

Write code to loop over nodes 0 to 3. If visited[node] is false, call dfs(node, -1). If dfs returns true, print true and stop. If no cycle found after loop, print false.

DSA Typescript

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

function dfs(node: number, parent: number): boolean {
  visited[node] = true;
  for (const neighbor of graph[node]) {
    if (!visited[neighbor]) {
      if (dfs(neighbor, node)) {
        return true;
      }
    } else if (neighbor !== parent) {
      return true;
    }
  }
  return false;
}

// Check for cycle and print result
# Your code here

Hint

Loop through all nodes and call dfs if not visited. Print true if cycle found, else false.