Graph Traversal: BFS and DFS

Introduction

In our last session, we learned how to represent graphs in Python, focusing on the adjacency list as a space-efficient method for the sparse graphs commonly found in real-world problems. Now that we know how to store a graph's structure, we're ready to explore it.

Today's learning outcome is to implement Breadth-First Search (BFS) and Depth-First Search (DFS) for graph traversal. "Traversal" simply means systematically visiting every vertex and edge in a graph. BFS and DFS are the two most fundamental strategies for doing this. They are the building blocks for many advanced graph algorithms used in everything from finding the shortest route on a map to analyzing social networks.

The core difference between them is the order in which they explore vertices.

Let's begin by understanding the high-level concepts behind these two approaches.

Conceptual Overview: BFS vs. DFS

The best way to understand BFS and DFS is through analogy.

• Breadth-First Search (BFS) is like the ripple effect from a stone thrown into a pond. It starts at a source vertex and explores its immediate neighbors first. Then, it moves to the next "layer" of vertices (the neighbors of the neighbors) and so on. It explores the graph broadly.
• Depth-First Search (DFS) is like exploring a maze. You pick a path and follow it as deeply as you can. When you hit a dead end, you backtrack to the last junction and try a different path. It explores the graph deeply.

To achieve these different strategies, they use different data structures:

• BFS uses a Queue (First-In, First-Out). This ensures that you process vertices in the order they were discovered, maintaining the layer-by-layer exploration.
• DFS uses a Stack (Last-In, First-Out). This can be an explicit stack in your code or the implicit function call stack used by recursion. This "last-in, first-out" behavior is what causes the algorithm to dive deep into the most recently discovered path.

The following short video provides a great visual sketch of these ideas.

Now, let's dive into the implementation details of each algorithm.

Depth-First Search (DFS): The Deep Dive

As the name implies, DFS ventures as far as possible down each branch before backtracking. This "deep" exploration is very useful for tasks like maze-solving, cycle detection, and topological sorting.

A crucial component of any graph traversal is a way to track which vertices have already been visited. Without this, if the graph contains a cycle, the algorithm would loop infinitely. We'll use a set in Python, which we'll call visited or seen, to keep track.

There are two common ways to implement DFS: recursively and iteratively.

1. Recursive DFS

The recursive approach is often more intuitive because the concept of "backtracking" is handled automatically by the function call stack.

The logic is simple:

1. Start at a given node.
2. Mark it as visited and process it (e.g., print it).
3. For each of its neighbors:
   • If the neighbor has not been visited, recursively call the DFS function on that neighbor.

This process continues until all reachable nodes have been visited.

2. Iterative DFS

While recursion is elegant, it can cause a "maximum recursion depth exceeded" error in Python for very large or deep graphs. The iterative approach avoids this by using an explicit stack data structure.

The logic is as follows:

1. Initialize a stack with the starting node.
2. Initialize a visited set.
3. While the stack is not empty:
   • Pop a node from the stack.
   • If this node hasn't been visited:
     • Mark it as visited and process it.
     • Push all its unvisited neighbors onto the stack.

Let's watch a detailed walkthrough that covers the concepts and Python code for both recursive and iterative DFS.

Breadth-First Search (BFS): The Ripple Effect

BFS explores the graph in layers, finding all nodes at a distance of 1 from the start, then all nodes at a distance of 2, and so on. This property makes it perfect for finding the shortest path between two nodes in an unweighted graph.

The key to BFS is the queue (First-In, First-Out).

The logic for BFS is:

1. Initialize a queue with the starting node.
2. Initialize a visited set and add the starting node to it.
3. While the queue is not empty:
   • Dequeue a node from the front of the queue and process it.
   • For each of its neighbors:
     • If the neighbor has not been visited:
       • Mark it as visited.
       • Enqueue the neighbor.

To implement an efficient queue in Python, we use the deque object from the collections module. It allows for fast additions (append) and removals (popleft) from either end.

Let's see the BFS algorithm explained and coded.

Implementation Summary in Python

Let's consolidate what we've learned into a single Python script. Here, we'll first create a graph using the adjacency list representation (defaultdict) that you learned in the previous lesson. Then, we'll implement all three traversal methods: recursive DFS, iterative DFS, and BFS.

from collections import defaultdict, deque

# Class to represent a graph
class Graph:
    def __init__(self):
        # Adjacency list representation using defaultdict
        self.graph = defaultdict(list)

    def add_edge(self, u, v):
        # For an undirected graph, add edges both ways
        self.graph[u].append(v)
        self.graph[v].append(u)

    # --- Recursive DFS ---
    def dfs_recursive_util(self, v, visited):
        # Mark the current node as visited and print it
        visited.add(v)
        print(v, end=' ')

        # Recur for all the vertices adjacent to this vertex
        for neighbour in self.graph[v]:
            if neighbour not in visited:
                self.dfs_recursive_util(neighbour, visited)

    def dfs_recursive(self, start_node):
        print("Recursive DFS starting from node", start_node, ":")
        visited = set()
        self.dfs_recursive_util(start_node, visited)
        print("\n")

    # --- Iterative DFS ---
    def dfs_iterative(self, start_node):
        print("Iterative DFS starting from node", start_node, ":")
        visited = set()
        stack = [start_node]

        while stack:
            v = stack.pop()
            if v not in visited:
                visited.add(v)
                print(v, end=' ')
                # Push unvisited neighbors to the stack
                # Push them in reverse order to mimic recursive behavior
                for neighbour in reversed(self.graph[v]):
                    if neighbour not in visited:
                        stack.append(neighbour)
        print("\n")

    # --- Breadth-First Search (BFS) ---
    def bfs(self, start_node):
        print("BFS starting from node", start_node, ":")
        visited = set()
        queue = deque([start_node])
        visited.add(start_node)

        while queue:
            # Dequeue a vertex from the front
            v = queue.popleft()
            print(v, end=' ')

            # Get all adjacent vertices. If an adjacent has not
            # been visited, then mark it visited and enqueue it
            for neighbour in self.graph[v]:
                if neighbour not in visited:
                    visited.add(neighbour)
                    queue.append(neighbour)
        print("\n")


# --- Main driver code ---
if __name__ == '__main__':
    g = Graph()
    # Using the graph from the image at the start of the lesson
    g.add_edge('a', 'b')
    g.add_edge('a', 'c')
    g.add_edge('b', 'd')
    g.add_edge('b', 'e')
    g.add_edge('c', 'f')
    g.add_edge('c', 'g')

    start = 'a'
    g.dfs_recursive(start)
    g.dfs_iterative(start)
    g.bfs(start)

# Expected Output:
# Recursive DFS starting from node a :
# a b d e c f g 
#
# Iterative DFS starting from node a :
# a b d e c f g 
#
# BFS starting from node a :
# a b c d e f g 

Complexity and Applications

Both DFS and BFS visit each vertex and each edge exactly once. Therefore, their time complexity is $O(V+E)$, where $V$ is the number of vertices and $E$ is the number of edges. This assumes an adjacency list representation, which allows you to find all neighbors of a node in time proportional to its number of neighbors. The space complexity is $O(V)$ to store the visited set and the stack or queue.

You can explore a visualizer and more applications on the VisuAlgo website.

Conclusion

Congratulations! You have just implemented two of the most fundamental algorithms in computer science.

Key Takeaways:

• Graph Traversal is the process of visiting every vertex and edge in a graph.
• Depth-First Search (DFS) explores as deeply as possible before backtracking. It's naturally implemented with recursion or an explicit stack.
• Breadth-First Search (BFS) explores layer by layer. It is implemented with a queue (deque in Python).
• Both algorithms require a visited set to avoid infinite loops in graphs with cycles.
• The time complexity for both is $O(V+E)$.

Preview of the Next Lesson:

BFS and DFS are considered uninformed search algorithms because they explore systematically without any extra information about the goal. In our next module, we will encounter A Search*, an informed search algorithm that uses a heuristic (an educated guess) to find paths more efficiently. The foundational knowledge of graph traversal you gained today will be essential for understanding how A* works.