Graph Traversal: BFS and DFS

Analogy categoryAnalogies

Introduction

Graph traversal means systematically visiting every reachable vertex from a starting point. The two foundational strategies are Breadth-First Search (BFS), which explores level by level using a queue, and Depth-First Search (DFS), which explores as deep as possible before backtracking using a stack (or recursion). These two algorithms underpin nearly every advanced graph technique, from shortest paths to cycle detection to topological sorting.

🏏

Cricket analogy: Like scouting a talent network — BFS checks every player one degree of connection away before moving further out (like checking all teammates before teammates-of-teammates), while DFS follows one chain of connections as deep as possible, like tracing a single mentor-to-mentee lineage to its end before backtracking.

Representation/Syntax

python

from collections import deque, defaultdict

def bfs(graph, start):
    visited = {start}
    order = []
    queue = deque([start])
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return order

def dfs(graph, start):
    visited = set()
    order = []

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

    _dfs(start)
    return order

Explanation

BFS uses a FIFO queue: it visits the start node, then all its direct neighbors, then all neighbors of those neighbors, and so on. This guarantees that when BFS first reaches a node in an unweighted graph, it has found the shortest path (in number of edges) to it. DFS uses a LIFO structure (the call stack via recursion, or an explicit stack) to plunge deep along one path before backtracking, which makes it well suited for tasks like cycle detection, connected component discovery, and topological sorting.

🏏

Cricket analogy: BFS with a FIFO queue visits every player one handshake away before the next ring outward, guaranteeing it finds the shortest chain of introductions to a target player first; DFS with a LIFO stack follows one chain of introductions as deep as possible, which suits tasks like checking whether a group forms a closed circle (cycle) of mutual acquaintances.

Example

python

def dfs_iterative(graph, start):
    visited = set()
    order = []
    stack = [start]
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        order.append(node)
        for neighbor in reversed(graph[node]):
            if neighbor not in visited:
                stack.append(neighbor)
    return order

graph = defaultdict(list, {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'D'],
    'D': ['B', 'C', 'E'],
    'E': ['D']
})

print('BFS:', bfs(graph, 'A'))
print('DFS recursive:', dfs(graph, 'A'))
print('DFS iterative:', dfs_iterative(graph, 'A'))

Complexity

Both BFS and DFS run in O(V + E) time because every vertex is enqueued/pushed once and every edge is examined once when scanning adjacency lists. Space complexity is O(V) for the visited set plus the queue or stack, which can hold up to O(V) elements in the worst case (e.g., a star graph for BFS, or a linear chain for DFS recursion depth).

🏏

Cricket analogy: Both scouting methods touch every player once and every connection once, so total effort is O(V+E); the tracking notepad needs room for O(V) names, which can balloon if one star player is connected to everyone (BFS) or if the chain of mentors is one long unbroken line (DFS's memory of the whole chain).

Key Takeaways

BFS uses a queue and explores level by level; it finds shortest paths in unweighted graphs.
DFS uses a stack or recursion and explores as deep as possible before backtracking.
Both run in O(V + E) time and O(V) space with an adjacency list.
DFS recursion can hit Python's recursion limit on very deep graphs; use the iterative version for large inputs.
A visited set is essential in both to avoid infinite loops in cyclic graphs.

Practice what you learned

1. What data structure does BFS use to track which node to visit next?

2. What is the time complexity of both BFS and DFS on a graph with V vertices and E edges?

3. Why does BFS guarantee the shortest path in an unweighted graph?

4. Which traversal is more natural to implement recursively due to using the call stack?

5. What must you maintain in both BFS and DFS to avoid infinite loops on a graph with cycles?

Was this page helpful?

Graph Representation

Shortest Path Algorithms

Topics covered

#Python#DataStructuresStudyNotes#DataStructures#GraphTraversalBFSAndDFS#Graph#Traversal#BFS#DFS#StudyNotes#SkillVeris