Why DFS Depth First Search on Graph in DSA C?

The Big Idea

What if you could explore every path in a maze without ever getting lost or repeating steps?

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 certain room starting from the entrance. Trying to check every possible path by hand would be confusing and take forever.

The Problem

Manually exploring each path can be slow and easy to get lost. You might repeat the same paths again and again or miss some rooms. It is hard to keep track of where you have been and where to go next without a clear plan.

The Solution

Depth First Search (DFS) helps by exploring one path deeply before backtracking. It uses a simple rule: go as far as possible along one path, then back up and try another. This way, you systematically visit all connected rooms without missing or repeating.

Before vs After

✗ Before

void explore(int current) {
  // try all neighbors manually
  if (neighbor1 not visited) explore(neighbor1);
  if (neighbor2 not visited) explore(neighbor2);
  // ...
}

✓ After

void dfs(int current) {
  visited[current] = 1;
  for (int i = 0; i < graph[current].size(); i++) {
    int neighbor = graph[current][i];
    if (!visited[neighbor]) dfs(neighbor);
  }
}

What It Enables

DFS enables efficient and complete exploration of all connected parts of a graph or maze, making complex problems manageable.

Real Life Example

Finding all friends connected to you in a social network by exploring friend connections deeply before moving to other groups.

Key Takeaways

Manual path checking is slow and error-prone.

DFS explores deeply along one path before backtracking.

DFS systematically visits all connected nodes without repetition.