Graph Traversal with BFS and DFS

Graphs: The Language of Connection

Before we can traverse a graph, we need a common language to describe one. A graph is simply a collection of nodes (or vertices) connected by edges. Many real-world engineering problems can be modeled this way.

The video below offers an excellent, concise introduction to graph terminology and the common ways we represent them in code. The most important representation for our purposes today is the adjacency list.

An adjacency list is efficient because it gives us immediate access to a node's neighbors. In practice, this is often implemented using a hash map (or dictionary in Python), where each key is a node and its value is a list of its adjacent nodes.

The Two Traversal Strategies: Wide vs. Deep

BFS and DFS are two distinct strategies for visiting every node in a graph. The fundamental difference lies in the order they explore nodes.

• Breadth-First Search (BFS) explores layer by layer. It visits all of a node's immediate neighbors before moving on to the next level of neighbors. Think of it as the ripples spreading from a stone dropped in a pond.
• Depth-First Search (DFS) explores as far as possible along one path before backtracking. It dives deep into a branch, and only when it hits a dead end does it return to explore an alternative path. Think of this as navigating a maze.

The image below provides a clear visual comparison of their traversal orders on the same graph structure.

Breadth-First Search (BFS): The Shortest Path Finder

Because BFS expands level by level, it has a very important property: in an unweighted graph, it naturally finds the shortest path from the starting node to all other nodes. This makes it invaluable for problems like finding the shortest route in a network or the fewest steps to solve a puzzle.

To achieve this level-by-level traversal, BFS uses a Queue, which follows a First-In, First-Out (FIFO) principle.

The algorithm works as follows:

1. Initialize a queue and add the starting node.
2. Create a visited set and add the starting node to it to avoid cycles and redundant work.
3. While the queue is not empty:
   a. Dequeue a node (let's call it current).
   b. Process current.
   c. For each neighbor of current:
   i. If the neighbor has not been visited, add it to the visited set and enqueue it.

The following video from Abdul Bari provides an excellent, detailed walkthrough of this process.

Depth-First Search (DFS): The Path Explorer

DFS is the algorithm of choice for problems where you need to explore every possible path, such as maze-solving, finding connected components in a network, or checking for cycles. It's also the foundation for more advanced algorithms like backtracking.

To achieve its deep-diving behavior, DFS uses a Stack, which follows a Last-In, First-Out (LIFO) principle. In many cases, this stack is managed implicitly by the program's call stack when using a recursive implementation.

The algorithm can be implemented both iteratively and recursively.

Iterative DFS (with an explicit stack):

1. Initialize a stack and add the starting node.
2. Create a visited set.
3. While the stack is not empty:
   a. Pop a node from the stack (current).
   b. If current has been visited, skip to the next iteration.
   c. Mark current as visited and process it.
   d. For each neighbor of current, push it onto the stack.

Recursive DFS:

1. Define a function dfs(node, visited_set).
2. Mark the node as visited and process it.
3. For each neighbor of node:
   a. If the neighbor has not been visited, recursively call dfs(neighbor, visited_set).

The following video provides a very clear explanation of both the recursive and iterative approaches to DFS.

Implementation and Problem-Solving Patterns

Now that you have the conceptual foundation, let's look at how to implement these algorithms and, more importantly, when to use them.

As an engineering manager, one of the most valuable skills is quickly recognizing which tool is right for a given job. The following resource provides an excellent mental checklist for deciding between DFS and BFS.

Complexity Analysis

Finally, let's briefly touch on the performance of these algorithms. Let $V$ be the number of vertices and $E$ be the number of edges in the graph.

• Time Complexity: For both BFS and DFS, the time complexity is $O(V+E)$. This is because, in the worst case, we must visit every vertex ($V$) and traverse every edge ($E$) exactly once.

• Space Complexity: This is where the two algorithms differ significantly.

  • BFS: The space complexity is proportional to the maximum width of the graph, $O(W)$. In a "bushy" graph that expands rapidly, the queue can hold many nodes at a single level. In the worst case of a complete graph, this can be $O(V)$.
  • DFS: The space complexity is proportional to the maximum depth of the graph, $O(H)$. For a "long and skinny" graph, the recursion stack can become very deep. In the worst case, this can also be $O(V)$.

The choice between them can sometimes be dictated by memory constraints if the graph has a known shape (e.g., very wide vs. very deep).

Conclusion

In this lesson, we've explored the two fundamental workhorses of graph traversal. You now have the knowledge to navigate connected data structures efficiently.

Here are the essential takeaways:

• BFS (Breadth-First Search):
  • Strategy: Explores level by level, "wide" before "deep."
  • Data Structure: Queue (FIFO).
  • Best For: Finding the shortest path in an unweighted graph, level-order tree traversal.
• DFS (Depth-First Search):
  • Strategy: Explores one path to its conclusion before backtracking.
  • Data Structure: Stack (LIFO), often implemented with recursion.
  • Best For: Checking for path existence, detecting cycles, exploring all possibilities (e.g., solving a maze), and as a foundation for backtracking.
• Performance: Both have a time complexity of $O(V+E)$. Their space complexity depends on the graph's shape—BFS is sensitive to width ($O(W)$), while DFS is sensitive to height ($O(H)$).

In our next lesson, we will venture into a new and powerful algorithmic paradigm: dynamic programming. You will learn how to solve the classic 0/1 Knapsack problem, which will introduce you to techniques for breaking down complex optimization problems into simpler, overlapping subproblems.