Graph Traversals

Graph Traversals: BFS and DFS

In our previous lessons, we discussed what graphs are and how to represent them in code using Adjacency Lists and Adjacency Matrices.

Now that we have our data safely stored inside a graph, how do we search through it? If you are looking for a specific friend in a massive social network, you need a highly methodical way to search connection by connection so you don't get stuck in an infinite loop. Let's look at the two primary solutions.

1. Breadth-First Search (BFS)

Breadth-First Search (BFS) explores a graph layer by layer, moving uniformly outward from the starting node.

It visits all the direct neighbors of the starting node first. Once all the immediate neighbors have been checked, it moves one step further out to check the neighbors' neighbors, and so on.

Real-Life Analogy

Think of throwing a stone into a still pond. The ripples move outward in perfect, expanding concentric circles. BFS works the exact same way. Another analogy: Searching for someone in a building. You search your entire current floor first (your immediate neighbors) before you take the stairs to search the next floor.

The Secret Weapon: A Queue

To ensure BFS explores evenly and doesn't accidentally skip ahead, it relies entirely on a Queue data structure (First-In, First-Out).

1. You start at Node A. Mark it as visited and place its neighbors (B, C) in the queue.
2. You take the first item out of the queue (B). Visit it, and put its unvisited neighbors in the back of the queue.
3. You repeat this until the queue is completely empty!

Breadth-First Search goes wide, while Depth-First Search goes deep.

Coding BFS in Python

Let's write out a simple BFS algorithm using an Adjacency List. We will use Python's built-in collections.deque for blazing-fast queue operations.

from collections import deque

# Representing the graph from the image as an Adjacency List
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F', 'G'],
    'D': [],
    'E': [],
    'F': [],
    'G': []
}
def bfs(graph, start_node):
    visited = set()         # To keep track of visited nodes
    queue = deque([start_node]) # Initialize queue with start node
    visited.add(start_node)
    while queue:
        # Dequeue a vertex from the front of the queue
        current = queue.popleft()
        print(current, end=" ")
        # Get all adjacent vertices of the dequeued vertex. 
        # If an adjacent has not been visited, mark it visited and enqueue it.
        for neighbor in graph[current]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
print("BFS Traversal Order:")
bfs(graph, 'A')

2. Depth-First Search (DFS)

Depth-First Search (DFS) takes the exact opposite approach. Instead of checking neighbors first, it picks one single path and walks as far down that path as it possibly can.

When it hits a dead end, it backtracks to the last intersection and tries the next path.

Real-Life Analogy

Think of exploring a massive maze. You don't try taking one step down every single hallway simultaneously. Instead, you pick the left wall, walk down it until you hit a dead end, turn around, and take the very next branch you find.

The Secret Weapon: A Stack (or Recursion)

While BFS uses a Queue, DFS naturally uses a Stack (Last-In, First-Out). The easiest way to utilize a stack in programming is simply by using recursive function calls (the Call Stack)!

Coding DFS in Python

Let's write out DFS for the exact same graph. Because we use recursion, the code is incredibly short and elegant.

# Reusing the same graph
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F', 'G'],
    'D': [],
    'E': [],
    'F': [],
    'G': []
}

def dfs(graph, current_node, visited=None):
    # Initialize the set on the first run
    if visited is None:
        visited = set()
    # Mark current node as visited and print it
    visited.add(current_node)
    print(current_node, end=" ")
    # Recurse for all unvisited neighbors (going deep!)
    for neighbor in graph[current_node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)
print("DFS Traversal Order:")
dfs(graph, 'A')

3. Complexity & When to Use Which?

Both BFS and DFS share the exact same time complexity because they both visit every node and every edge exactly one time.

• Time Complexity: O(V + E) (Where V is the number of Vertices, and E is the number of Edges).
• Space Complexity: O(V) to keep track of the visited set and the memory needed for the Queue or the Recursive Call Stack.

So, if they have the same performance speeds, how do you choose between them during a technical interview?