Graphs, BFS and DFS

What is a graph?

A graph is a set of vertices (also called nodes) connected by edges. It is the most general way to describe how things are connected:

• Maps: places are vertices, roads are edges. "What's the quickest route?" is a graph question.
• Social networks: people are vertices, friendships are edges.
• The web: pages are vertices, links are edges.
• Course prerequisites: subjects are vertices, and "take A before B" is an edge. See Course Schedule in the lab.

Trees are a special kind of graph: connected, with no cycles. A general graph can have cycles, disconnected pieces, and any number of edges per vertex.

Graphs come in a few flavours:

Storing a graph

The usual representation is an adjacency list: for every vertex, keep a list of its neighbours. It uses O(V + E) memory for V vertices and E edges, and listing a vertex's neighbours is as fast as it can be.

The alternative is an adjacency matrix, a V × V grid where matrix[u][v] says whether there is an edge. Checking one edge is O(1), but it uses O(V²) memory even when there are few edges. Use it only for small, dense graphs.

The program below uses this graph with 7 vertices. Vertices 5 and 6 are connected to each other but not to the rest, so the graph has two connected components.

  0 ── 1
  │    │
  2 ── 3 ── 4        5 ── 6

Breadth-first search (BFS)

BFS explores the graph in rings: first the start vertex, then all its neighbours, then all their unvisited neighbours, and so on. It uses a queue, exactly like level-order traversal of a tree. Because it reaches vertices in order of distance, the first time BFS reaches a vertex is along a shortest path (counting edges). Recording each vertex's parent lets you rebuild that path afterwards.

Depth-first search (DFS)

DFS goes as deep as it can along one path before backing up and trying the next branch, like exploring a maze with one hand on the wall. It uses a stack, usually the call stack through recursion. DFS doesn't find shortest paths, but it is the natural tool for:

• Connected components: start a DFS from every unvisited vertex; each start is a new component. Number of Islands in the lab is this, on a grid.
• Cycle detection and topological sorting of directed graphs.
• Exploring every possibility, as in puzzles and backtracking.

In the output below, BFS visits 0 1 2 3 4 (by distance), while DFS visits 0 1 3 2 4: it follows 0 → 1 → 3 all the way down before coming back for 2.

Building one yourself

from collections import deque


class Graph:
    """An undirected graph on vertices 0..n-1, stored as an adjacency list."""

    def __init__(self, n):
        self.adj = [[] for _ in range(n)]

    def add_edge(self, u, v):
        self.adj[u].append(v)
        self.adj[v].append(u)  # undirected: the edge works both ways

    def bfs(self, start):
        """Visit order, distance (in edges) and parent of every vertex reachable from start."""
        dist = [-1] * len(self.adj)
        parent = [-1] * len(self.adj)
        dist[start] = 0
        order, queue = [], deque([start])
        while queue:
            u = queue.popleft()
            order.append(u)
            for v in self.adj[u]:
                if dist[v] == -1:  # mark when discovered, so nothing is queued twice
                    dist[v] = dist[u] + 1
                    parent[v] = u
                    queue.append(v)
        return order, dist, parent

    def shortest_path(self, start, goal):
        _, dist, parent = self.bfs(start)
        if dist[goal] == -1:
            return None
        path, v = [], goal
        while v != -1:  # walk back along the parents, then reverse
            path.append(v)
            v = parent[v]
        return path[::-1]

    def dfs(self, start):
        order, seen = [], [False] * len(self.adj)

        def visit(u):
            seen[u] = True
            order.append(u)
            for v in self.adj[u]:
                if not seen[v]:
                    visit(v)

        visit(start)
        return order

    def components(self):
        seen, count = [False] * len(self.adj), 0
        for s in range(len(self.adj)):
            if not seen[s]:
                count += 1
                for u in self.dfs(s):
                    seen[u] = True
        return count


def joined(values):
    return " ".join(str(v) for v in values)


g = Graph(7)
for u, v in ((0, 1), (0, 2), (1, 3), (2, 3), (3, 4), (5, 6)):
    g.add_edge(u, v)
for u, neighbours in enumerate(g.adj):
    print(f"{u}: {joined(neighbours)}")
order, dist, _ = g.bfs(0)
print("BFS from 0:", joined(order))
print("distances from 0:", joined(dist))
print("shortest path 0 -> 4:", " -> ".join(str(v) for v in g.shortest_path(0, 4)))
print("path 0 -> 6:", "none" if g.shortest_path(0, 6) is None else "found")
print("DFS from 0:", joined(g.dfs(0)))
print("connected components:", g.components())

0: 1 2
1: 0 3
2: 0 3
3: 1 2 4
4: 3
5: 6
6: 5
BFS from 0: 0 1 2 3 4
distances from 0: 0 1 1 2 3 -1 -1
shortest path 0 -> 4: 0 -> 1 -> 3 -> 4
path 0 -> 6: none
DFS from 0: 0 1 3 2 4
connected components: 2

Distances of -1 mean "not reachable from 0". That is how BFS tells you vertices 5 and 6 are in another component.

Operations and their cost

BFS and DFS visit each vertex once and look along each edge once (twice for undirected edges), which is where O(V + E) comes from.

Beyond BFS and DFS

• Weighted shortest paths: when edges have different costs, BFS is no longer enough. Dijkstra's algorithm replaces the queue with a priority queue.
• Topological sort: order the vertices of a directed acyclic graph so every edge points forward. Kahn's algorithm, used in Course Schedule, repeatedly takes vertices with no remaining incoming edges.
• Union–find: a fast way to track connected components while edges are being added.

Common mistakes

• Not marking visited vertices. In a graph with cycles, BFS and DFS loop forever without a seen (or dist) check.
• Marking too late in BFS. Mark a vertex when you add it to the queue, not when you take it out, or the same vertex can be queued many times.
• Assuming the graph is connected. Loop over all vertices and start a new search from each unvisited one.
• Using DFS for shortest paths. DFS finds a path, not the shortest. Use BFS for unweighted graphs.
• Deep recursion. DFS on a long chain of vertices can overflow the call stack; use an explicit stack for very large graphs.

When to use which

Use BFS when you need the fewest steps: shortest routes, the nearest something, or level-by-level processing. Use DFS when you need to explore everything reachable, find components, detect cycles or order tasks. When either would work, pick whichever you find easier to write, because both are O(V + E).