Data Structures & Algorithms Cheatsheet

Graphs and BFS/DFS

Use this Data Structures & Algorithms reference while you build software engineering projects, review code, or refresh the syntax you reach for most.

Complexity

For V vertices and E edges. Traversal cost is O(V + E) in adjacency-list form, because every vertex and every edge is touched once.

Operation	Adjacency list	Adjacency matrix
space	O(V + E)	O(V²)
add edge	O(1)	O(1)
check if edge (u, v) exists	O(deg u)	O(1)
iterate neighbors of u	O(deg u)	O(V)
BFS or DFS	O(V + E)	O(V²)
connected components	O(V + E)	O(V²)
cycle detection	O(V + E)	O(V²)
grid as a graph, r × c	O(rc)	—

Use a matrix only for dense graphs or when you need O(1) edge lookup. Everything else is an adjacency list.

Representations

from collections import defaultdict, deque

# adjacency list from an edge list
g = defaultdict(list)
for u, v in edges:
    g[u].append(v)
    g[v].append(u)         # omit this line for a directed graph

# weighted
wg = defaultdict(list)
for u, v, w in edges:
    wg[u].append((v, w))

# adjacency matrix
m = [[0] * n for _ in range(n)]
for u, v in edges:
    m[u][v] = m[v][u] = 1

# a grid IS a graph: cells are vertices, 4 or 8 neighbors are edges
DIRS4 = ((1, 0), (-1, 0), (0, 1), (0, -1))
DIRS8 = DIRS4 + ((1, 1), (1, -1), (-1, 1), (-1, -1))

Graph term	Meaning
degree	number of incident edges, in-degree and out-degree when directed
path	sequence of vertices connected by edges, no repeats
cycle	path returning to its start
connected component	maximal set of mutually reachable vertices (undirected)
strongly connected	mutually reachable in a directed graph
DAG	directed acyclic graph, has a topological order
bipartite	2-colorable, equivalently no odd-length cycle
tree	connected, acyclic, exactly V − 1 edges

BFS

Explores in layers, so on an unweighted graph the first time you reach a vertex is via a shortest path. Mark visited when enqueuing, not when dequeuing.

def bfs(g, start):
    """Visit order plus distance from start. O(V + E)."""
    dist = {start: 0}
    q = deque([start])
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in g[u]:
            if v not in dist:
                dist[v] = dist[u] + 1
                q.append(v)            # mark on enqueue, not on dequeue
    return order, dist

def shortest_path(g, start, goal):
    """Reconstruct the path via a parent map."""
    parent = {start: None}
    q = deque([start])
    while q:
        u = q.popleft()
        if u == goal:
            path = []
            while u is not None:
                path.append(u)
                u = parent[u]
            return path[::-1]
        for v in g[u]:
            if v not in parent:
                parent[v] = u
                q.append(v)
    return []

def bfs_grid(grid, src, dst):
    """Fewest steps between two cells, or -1. '1' is a wall."""
    rows, cols = len(grid), len(grid[0])
    sr, sc = src
    if grid[sr][sc] == "1":
        return -1
    seen = [[False] * cols for _ in range(rows)]
    seen[sr][sc] = True
    q = deque([(sr, sc)])
    steps = 0
    while q:
        for _ in range(len(q)):        # one ring per iteration
            cell = q.popleft()
            if cell == dst:
                return steps
            r, c = cell
            for dr, dc in DIRS4:
                nr, nc = r + dr, c + dc
                if (0 <= nr < rows and 0 <= nc < cols
                        and not seen[nr][nc] and grid[nr][nc] != "1"):
                    seen[nr][nc] = True
                    q.append((nr, nc))
        steps += 1                     # increment after the ring drains
    return -1

Multi-source BFS seeds the queue with every source at distance 0. That solves "nearest gate from each cell" and "rotting oranges" in one pass instead of V passes.

def multi_source_bfs(grid, sources):
    dist = [[-1] * len(grid[0]) for _ in grid]
    q = deque()
    for r, c in sources:
        dist[r][c] = 0
        q.append((r, c))
    while q:
        r, c = q.popleft()
        for dr, dc in DIRS4:
            nr, nc = r + dr, c + dc
            if (0 <= nr < len(grid) and 0 <= nc < len(grid[0])
                    and dist[nr][nc] == -1):
                dist[nr][nc] = dist[r][c] + 1
                q.append((nr, nc))
    return dist

DFS

Goes deep first. Natural for connectivity, cycle detection, and anything where the answer at a vertex depends on its subtree.

def dfs_recursive(g, u, seen=None):
    if seen is None:
        seen = set()
    seen.add(u)
    for v in g[u]:
        if v not in seen:
            dfs_recursive(g, v, seen)
    return seen

def dfs_iterative(g, start):
    """Explicit stack, no recursion limit risk."""
    seen, st, order = set(), [start], []
    while st:
        u = st.pop()
        if u in seen:
            continue
        seen.add(u)                    # mark on POP for a stack
        order.append(u)
        for v in reversed(g[u]):       # reversed to match recursive order
            if v not in seen:
                st.append(v)
    return order

def count_islands(grid):
    """Flood fill each unvisited land cell. O(rc)."""
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    count = 0

    def sink(r, c):
        st = [(r, c)]
        while st:
            cr, cc = st.pop()
            for dr, dc in DIRS4:
                nr, nc = cr + dr, cc + dc
                if (0 <= nr < rows and 0 <= nc < cols
                        and grid[nr][nc] == "1"):
                    grid[nr][nc] = "0"     # mark in place
                    st.append((nr, nc))

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1":
                count += 1
                grid[r][c] = "0"
                sink(r, c)
    return count

// Java: iterative DFS on a grid with an int-encoded stack
Deque<int[]> st = new ArrayDeque<>();
st.push(new int[]{r, c});
while (!st.isEmpty()) {
    int[] cur = st.pop();
    for (int[] d : DIRS) {
        int nr = cur[0] + d[0], nc = cur[1] + d[1];
        if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
                && grid[nr][nc] == '1') {
            grid[nr][nc] = '0';
            st.push(new int[]{nr, nc});
        }
    }
}

BFS Or DFS

Need	Use
shortest path, unweighted	BFS
shortest path, weighted non-negative	Dijkstra
shortest path, weights 0 or 1	0-1 BFS with a deque
any path exists, connectivity	either, DFS uses less memory on deep graphs
all paths, all permutations	DFS with backtracking
cycle detection, directed	DFS with three colors
cycle detection, undirected	DFS with a parent check, or union-find
topological order	DFS postorder, or Kahn's BFS
level or ring structure	BFS
bipartite check	either, BFS is easier to reason about
minimum steps in a state space	BFS

Memory profile. BFS holds a whole frontier, which is O(V) on wide graphs. DFS holds a path, which is O(V) on deep graphs. On a wide shallow graph DFS wins, on a deep narrow graph BFS wins.

Cycle Detection And Bipartite Check

def has_cycle_directed(n, edges):
    """Three colors: 0 unvisited, 1 in the current path, 2 finished."""
    g = defaultdict(list)
    for u, v in edges:
        g[u].append(v)
    color = [0] * n

    def dfs(u):
        color[u] = 1
        for v in g[u]:
            if color[v] == 1:
                return True            # back edge to the active path
            if color[v] == 0 and dfs(v):
                return True
        color[u] = 2
        return False

    return any(color[u] == 0 and dfs(u) for u in range(n))

def has_cycle_undirected(n, edges):
    """A visited neighbor that is not the parent closes a cycle."""
    g = defaultdict(list)
    for u, v in edges:
        g[u].append(v)
        g[v].append(u)
    seen = [False] * n

    def dfs(u, parent):
        seen[u] = True
        for v in g[u]:
            if not seen[v]:
                if dfs(v, u):
                    return True
            elif v != parent:
                return True
        return False

    return any(not seen[u] and dfs(u, -1) for u in range(n))

def is_bipartite(n, g):
    """2-color with BFS. Fails exactly when an odd cycle exists."""
    color = [0] * n
    for s in range(n):
        if color[s]:
            continue
        color[s] = 1
        q = deque([s])
        while q:
            u = q.popleft()
            for v in g[u]:
                if color[v] == color[u]:
                    return False
                if color[v] == 0:
                    color[v] = -color[u]
                    q.append(v)
    return True

A single visited set is not enough for directed cycle detection. You must distinguish "on the current path" from "already finished", or a diamond-shaped DAG reports a false cycle.

State-Space BFS

Many problems are graphs in disguise. The vertex is a state, the edge is a legal move, and BFS gives the minimum number of moves.

def word_ladder(begin, end, word_list):
    """Minimum transformations changing one letter at a time. O(N * L * 26)."""
    words = set(word_list)
    if end not in words:
        return 0
    q = deque([(begin, 1)])
    seen = {begin}
    while q:
        word, steps = q.popleft()
        if word == end:
            return steps
        for i in range(len(word)):
            for ch in "abcdefghijklmnopqrstuvwxyz":
                nxt = word[:i] + ch + word[i + 1:]
                if nxt in words and nxt not in seen:
                    seen.add(nxt)
                    q.append((nxt, steps + 1))
    return 0

def open_lock(deadends, target):
    """4-dial lock, minimum turns. Classic state-space BFS."""
    dead = set(deadends)
    if "0000" in dead:
        return -1
    q, seen = deque([("0000", 0)]), {"0000"}
    while q:
        state, turns = q.popleft()
        if state == target:
            return turns
        for i in range(4):
            d = int(state[i])
            for nd in ((d + 1) % 10, (d - 1) % 10):
                nxt = state[:i] + str(nd) + state[i + 1:]
                if nxt not in seen and nxt not in dead:
                    seen.add(nxt)
                    q.append((nxt, turns + 1))
    return -1

Encode the state as something hashable: a tuple, a string, or a bitmask.

Gotchas

Mark visited on enqueue in BFS. Marking on dequeue lets the same vertex enter the queue many times, degrading to exponential work.
deque.popleft, never list.pop(0). The latter turns O(V + E) into O(V²).
Self-loops and parallel edges. The undirected parent check breaks on parallel edges. Track the edge index rather than the parent vertex when they are possible.
Disconnected graphs. Loop over every vertex as a potential start, or you only explore one component.
1-indexed input. Many problems number vertices from 1. Size arrays n + 1 or subtract 1 consistently.
Recursion depth. A 10⁵-vertex path graph overflows Python's stack. Use the iterative form or raise the limit.
Grid bounds before value. Check 0 <= nr < rows before reading grid[nr][nc], since Python's negative indices wrap silently instead of erroring.
Restore mutated state if the grid is needed again. Sinking islands in place is fine only when the input is disposable.