Visualizing Graph Traversal: DFS vs. BFS in Python

Introduction

Graphs are powerful data structures that model relationships among interconnected elements—think of social networks, recommendation systems, or network routing maps. Traversing graphs efficiently is a cornerstone skill for software engineers. In this blog, we’ll explore two fundamental traversal strategies: Depth-First Search (DFS) and Breadth-First Search (BFS). Using Python, we’ll implement each algorithm from scratch, visualize the order of traversal, and discuss when to choose one over the other.

1. Understanding the Problem and Graph Representation

Graphs can be represented as adjacency lists or matrices. For traversal algorithms, adjacency lists are often preferred for their space efficiency and flexibility.

# Simple undirected graph represented with a dictionary

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

print("Graph adjacency list:")
for node, neighbors in graph.items():
    print(f"{node}: {neighbors}")

This adjacency-list structure allows easy access to the neighbors of each node. In directed graphs, edges only go one way, but for now, we’ll assume an undirected graph.

2. Implementing Depth-First Search (DFS)

DFS explores as far as possible along each branch before backtracking, making it ideal for pathfinding, cycle detection, and connected component discovery.

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start, end=" ")

    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

print("\nDFS Traversal starting from A:")
dfs(graph, 'A')

How it works: Each time we visit a node, we mark it as visited and recursively visit all unvisited neighbors. This recursion uses the call stack to keep track of the exploration path, effectively emulating a stack-based approach.

Performance tip: DFS works well for large and deep graphs but can cause recursion depth issues in extremely large datasets. In such cases, an iterative DFS using an explicit stack can help.

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]

    while stack:
        node = stack.pop()
        if node not in visited:
            print(node, end=" ")
            visited.add(node)
            # reversed for consistent traversal order
            stack.extend(reversed(graph[node]))

print("\nIterative DFS Traversal starting from A:")
dfs_iterative(graph, 'A')

3. Implementing Breadth-First Search (BFS)

BFS explores all neighboring nodes at the present depth first before moving deeper. It is ideal for finding shortest paths in unweighted graphs or level-order traversals.

from collections import deque

def bfs(graph, start):
    visited = set([start])
    queue = deque([start])

    while queue:
        node = queue.popleft()
        print(node, end=" ")

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

print("\nBFS Traversal starting from A:")
bfs(graph, 'A')

How it works: BFS uses a queue to ensure that we process all nodes level by level. When a node is visited, all of its unvisited neighbors are enqueued. This makes BFS the go-to algorithm for shortest path tasks in unweighted graphs.

4. Comparing DFS and BFS

Let’s compare both based on traversal pattern and usage:

DFS — follows one branch deeply; uses recursion or stack.
BFS — explores neighbors level by level; uses a queue.

The output orders may differ, but both visit all reachable nodes.

# Sample Output
DFS Traversal: A B D E F C
BFS Traversal: A B C D E F

Performance Comparison

Time Complexity: O(V + E) for both, where V = vertices, E = edges.
Space Complexity: DFS = O(V) due to recursion stack; BFS = O(V) due to queue storage.

When to use DFS: Ideal for deep exploration, topological sorting, and detecting cycles.
When to use BFS: Perfect for shortest unweighted path, finding minimum hops, or level-wise exploration.

5. Real-world Applications and Visualization Tips

DFS and BFS are not just theoretical—they appear everywhere:

Web crawlers use BFS to index pages efficiently.
Maze solvers and game AI often rely on DFS to explore paths.
Social networks apply BFS for friend recommendations or connection paths.
Compilers and dependency managers utilize DFS for dependency resolution.

Visualization Tip: Use tools like networkx and matplotlib to plot your graph and highlight traversal steps visually. This can help you debug and understand traversal flows.

import networkx as nx
import matplotlib.pyplot as plt

G = nx.Graph(graph)
nx.draw(G, with_labels=True, node_color='lightblue', node_size=2000, font_weight='bold')
plt.title("Graph visualization of traversal example")
plt.show()

Conclusion

DFS and BFS are foundational graph traversal techniques that every Python developer should understand. Both offer unique advantages depending on the problem domain. By mastering their implementations, you’ll unlock the ability to handle complex data relationships—from network routing and search engines to machine learning graph embeddings. Experiment, visualize, and choose the right traversal based on context!

Useful links: