DSData Structures & Algorithms · Lesson 7 of 9

Graphs: BFS & DFS

A graph is nodes plus edges connecting them — no hierarchy required, cycles allowed. Social networks, road maps, the internet, package dependencies, game maps: when things connect to things, it's a graph.

Graphs generalize trees: any node can connect to any other, edges can be one-way (directed) or two-way (undirected), and loops are allowed. The standard representation is an adjacency list — a hash map from each node to the list of its neighbors. Nearly every graph question reduces to one operation: traversal, visiting nodes by following edges. Two orders matter: breadth-first (BFS) and depth-first (DFS).

Python


# Adjacency list: node -> neighbors
graph = {
    'you':    ['alice', 'bob'],
    'alice':  ['you', 'carol'],
    'bob':    ['you', 'carol', 'dave'],
    'carol':  ['alice', 'bob'],
    'dave':   ['bob'],
}

BFS explores in rings: all direct neighbors first, then neighbors-of-neighbors, and so on outward. It uses a queue (FIFO — the stacks & queues lesson) and a visited set to avoid going in circles. Because it expands one ring at a time, the first time BFS reaches a node is via a shortest path — which is why GPS-style 'fewest hops' problems are BFS.

Python


from collections import deque

def bfs_shortest(graph, start, goal):
    queue = deque([(start, 0)])       # (node, distance)
    visited = {start}
    while queue:
        node, dist = queue.popleft()
        if node == goal:
            return dist
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, dist + 1))
    return -1                          # unreachable

bfs_shortest(graph, 'you', 'dave')     # 2 (you -> bob -> dave)

DFS dives instead: follow one path as deep as it goes, back up, try the next. Swap the queue for a stack — or just use recursion, since the call stack is the stack. DFS answers 'is there any path?', finds connected components, and detects cycles (how npm and pip catch circular dependencies). BFS finds shortest; DFS goes deep. Choosing between them is usually the whole problem.

Python


def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)
    return visited

dfs(graph, 'you')     # every node reachable from 'you'

# Same algorithm, no recursion — explicit stack:
def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    while stack:
        node = stack.pop()            # pop = LIFO = depth-first
        if node not in visited:
            visited.add(node)
            stack.extend(graph[node])
    return visited

✦ Tip
Both traversals are O(V + E) — every node and edge visited once. The 'visited' set is not optional: without it, any cycle loops forever. Forgetting it is the single most common graph bug. Weighted shortest paths (roads with distances, not hops) need Dijkstra's algorithm — BFS with a priority queue instead of a plain queue.