A+DS

Depth-First Search

Go deep before going wide.

Like exploring a maze by always taking the next unexplored path and going as deep as possible before backtracking. DFS uses a stack to dive deep into one branch before exploring others.

     [ START ]
      |
      v
     [A] → [B] → [D]    go deep!
                       |
                    backtrack
                       |
              [C] → [E]      keep going

  Stack: [START] → [A] → [B] → [D] → back...

How it works

  1. 1Start at the source node, push it on a stack
  2. 2Pop the top node and visit it
  3. 3Push all unvisited neighbors onto the stack
  4. 4Repeat until the stack is empty

Loading...