Graphs, BFS, and DFS

Why it matters

A graph is a set of things (nodes or vertices) and connections between them (edges). Road maps, social networks, web links, package dependencies, network routers, molecules and game levels are all graphs. Two search strategies, breadth-first search (BFS) and depth-first search (DFS), answer most beginner graph questions: Can I get from A to B? What is the shortest route? Which parts are connected? Trees are just graphs with no cycles, so you already know half of this.

Representing a graph

The most common representation is an adjacency list: a dict from each node to the list of its neighbours.

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

This graph is undirected (if A connects to B, B lists A). In a directed graph, such as "package X depends on Y", edges go one way. A grid is a graph too: each open cell is a node, and its neighbours are the open cells up, down, left and right.

Unlike trees, graphs can have cycles (A -> B -> D -> C -> A). Any graph search must remember which nodes it has already visited, or it will loop forever.

Depth-first search (DFS)

DFS goes as deep as it can along one path, then backs up and tries the next. It is naturally recursive (or uses a stack).

def has_path(graph, start, goal, visited=None):
    if visited is None:
        visited = set()
    if start == goal:
        return True
    visited.add(start)
    for neighbour in graph.get(start, []):
        if neighbour not in visited:
            if has_path(graph, neighbour, goal, visited):
                return True
    return False

has_path(graph, "A", "E")   # True

DFS is good for "is there any path?", finding connected groups, detecting cycles and ordering dependencies. It does not guarantee the shortest path. (Note visited=None and a new set inside: a mutable default like visited=set() would be shared between calls.)

Breadth-first search (BFS)

BFS explores in rings: first every node one step away, then every node two steps away, and so on. It uses a queue (first in, first out). Because it reaches nodes in order of distance, the first time BFS reaches a node is by a shortest path (counting edges).

from collections import deque

def distances_from(graph, start):
    dist = {start: 0}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for neighbour in graph.get(node, []):
            if neighbour not in dist:          # dist doubles as "visited"
                dist[neighbour] = dist[node] + 1
                queue.append(neighbour)
    return dist

distances_from(graph, "A")   # {'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 3}

Mark a node as seen when you add it to the queue, not when you take it out, so it is never queued twice.

Worked example: shortest path in a grid

A maze is a list of strings, . for open and # for a wall. Find the fewest moves from the top-left to the bottom-right, moving up, down, left or right.

from collections import deque

def shortest_path_length(grid):
    if not grid or not grid[0]:
        return -1
    rows, cols = len(grid), len(grid[0])
    goal = (rows - 1, cols - 1)
    if grid[0][0] == "#" or grid[goal[0]][goal[1]] == "#":
        return -1
    queue = deque([(0, 0, 0)])          # row, col, steps so far
    seen = {(0, 0)}
    while queue:
        r, c, steps = queue.popleft()
        if (r, c) == goal:
            return steps
        for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == "." and (nr, nc) not in seen:
                seen.add((nr, nc))
                queue.append((nr, nc, steps + 1))
    return -1

maze = ["..#",
        ".##",
        "..."]
shortest_path_length(maze)   # 4: down, down, right, right

The pieces you will reuse in every grid problem: a bounds check, a wall check, a seen set, and a list of four directions. A one-cell open grid returns 0; a blocked start or goal returns -1.

Cost. BFS and DFS each visit every node and edge at most once: O(V + E) for V nodes and E edges. A grid with R rows and C columns is O(R x C).

BFS or DFS?

Common mistakes

• No visited set, so cycles cause infinite loops.
• Marking visited too late in BFS, so the same cell is queued many times.
• Using DFS for shortest paths. It finds a path, not necessarily the shortest.
• Off-by-one bounds checks (<= instead of <) that crash with IndexError.
• A mutable default visited=set() shared between separate calls.

Quick recap

• Graphs are nodes plus edges; store them as an adjacency list (dict of lists).
• DFS goes deep (recursion or a stack); BFS goes in rings (a deque).
• BFS finds the shortest path in an unweighted graph or grid.
• Always track visited nodes. Cost is O(V + E).

Try it

In the Do tab, write has_path with DFS and shortest_path_length with BFS on a grid. The checks include an empty grid, a single cell, blocked starts and unreachable goals.