Why DFS Depth First Search on Graph in DSA Typescript?

The Big Idea

What if you could explore every path without ever getting lost or repeating yourself?

The Scenario

Imagine you have a huge maze with many paths and rooms. You want to find if there is a way to reach a special room starting from the entrance. If you try to check every path by guessing randomly or writing down every step manually, it will take forever and you might get lost or repeat the same paths.

The Problem

Manually exploring each path in a maze is slow and confusing. You can easily miss some paths or go in circles. Writing down every step without a clear plan leads to mistakes and wastes time. It is hard to remember which rooms you already checked.

The Solution

Depth First Search (DFS) is like having a smart helper who explores one path deeply before backtracking and trying another. It remembers where it has been, so it never repeats rooms. This way, it quickly finds if the special room is reachable or not, without getting lost or confused.

Before vs After

✗ Before

function findRoom(maze, start, target) {
  // Try all paths randomly without tracking
  // May repeat rooms or miss paths
}

✓ After

function dfs(graph, node, visited) {
  if (visited.has(node)) return;
  visited.add(node);
  for (const neighbor of graph[node]) {
    dfs(graph, neighbor, visited);
  }
}

What It Enables

DFS enables systematic and efficient exploration of all connected parts of a graph or maze, ensuring no path is missed or repeated.

Real Life Example

Finding all friends in a social network starting from one person by exploring their friends, then friends of friends, and so on.

Key Takeaways

Manual path checking is slow and error-prone.

DFS explores deeply and remembers visited nodes.

DFS helps find connections or paths efficiently in graphs.