Overview

A graph is a set of vertices connected by edges. Roads between cities, friendships, web links, course prerequisites and the cells of a maze are all graphs. Trees are a special case — connected and without cycles — so everything you learned about tree traversal carries over, with one addition: because graphs can contain cycles, you must remember which vertices you have already visited.

Breadth-first search (BFS) explores in rings of increasing distance using a queue, so in an unweighted graph it finds shortest paths. Depth-first search (DFS) dives as deep as possible before backtracking, using recursion or a stack, and is the natural fit for connectivity, cycle detection and exploring every path. Both visit each vertex and edge once: O(V + E).

Key concepts

Tick a concept once you can explain it in your own words without notes.

Complexity cheat sheet

OperationCost
BFS / DFS (adjacency list)O(V + E) time, O(V) space
BFS / DFS (adjacency matrix)O(V²)
Grid traversalO(rows × cols)

Patterns to recognise

Flood fill / count components

Use it for: Number of islands, max area of island, provinces.

Loop over all vertices; start a traversal from each unvisited one and count.

Multi-source BFS

Use it for: Rotting oranges, walls and gates, distance to nearest 0.

Put every source in the queue at distance 0, then run one BFS.

Two-colouring

Use it for: Is graph bipartite, possible bipartition.

Colour neighbours opposite colours during BFS/DFS; a conflict means not bipartite.

Code template

Number of islands — BFS on a grid
from collections import deque


def num_islands(grid):
    rows, cols = len(grid), len(grid[0])
    islands = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != '1':
                continue
            islands += 1
            grid[r][c] = '0'                     # mark when enqueuing
            queue = deque([(r, c)])
            while queue:
                y, x = queue.popleft()
                for dy, dx in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                    ny, nx = y + dy, x + dx
                    if 0 <= ny < rows and 0 <= nx < cols and grid[ny][nx] == '1':
                        grid[ny][nx] = '0'
                        queue.append((ny, nx))
    return islands

Common mistakes

  • Marking visited when dequeuing instead of enqueuing lets the same cell enter the queue many times.
  • For undirected graphs, add each edge in both directions.
  • Graphs can be disconnected — loop over every vertex, not just vertex 0.
  • Recursive DFS on a 1000 × 1000 grid will overflow the stack in many languages; prefer BFS or an explicit stack.

Quick check

Three questions on BFS & DFS. Get all three right to earn +15 XP.

  1. An adjacency list for a graph with V vertices and E edges uses:

  2. In an unweighted graph, which algorithm finds the shortest path by number of edges?

  3. What goes wrong if a graph traversal has no visited set?

Challenges

Ordered from easiest to hardest. Solve them on LeetCode, then tick them off here. Know every concept and solve 3 to clear the level.

Stuck on BFS & DFS?Ask Orbi for a hint, a fresh explanation or a review of your code.

Ask the tutor