Lesson 7 of 9

Graphs: BFS & DFS

A graph is a of nodes connected by edges, with no required hierarchy. You'll learn to represent one and explore it with breadth-first and depth-first search.

Graphs generalize trees: any node can connect to any other, edges can be one-way (directed) or two-way (undirected), and are allowed. The standard representation is an adjacency — a 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).


# 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 & 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.


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 , since the call stack is the stack. DFS answers 'is there any path?', finds connected components, and detects cycles (how npm and catch circular dependencies). BFS finds shortest; DFS goes deep. Choosing between them is usually the whole problem.


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

Finished reading?Mark it done to track your progress.

Tip: use the ← and → keys to move between lessons.