Graph Field Notes

0Why graphs are not a new idea

You already know graphs. A linked list is nodes connected by next pointers. A tree is nodes connected by left and right pointers. A graph is the general case: nodes connected by pointers, with no rules about how many pointers a node has or where they go. Cycles are allowed. Disconnected pieces are allowed.

What you will be able to do after this page: read a graph in any of its three input formats, write matrix DFS and matrix BFS from memory, build an adjacency list from an edge list, and choose DFS or BFS on purpose instead of by habit.

1Vocabulary and the three input formats

Vertices and edges

In graph language, a node is a vertex (plural: vertices) and a pointer is an edge. There are no restrictions on where vertices are placed or how edges connect them. A vertex can have any number of edges: zero, one, or one to every other vertex. A set of vertices with no edges at all still counts as a graph.

How many edges can a graph with V vertices have? Each vertex can point to every vertex, including itself. With A, B, C: A can point to A, B, C; so can B; so can C. That is 3 × 3 = 9. In general E ≤ V² (assuming no duplicate edges). A graph that actually has V² edges is called a complete graph.

An edge with a direction (A → B, but not B → A) makes a directed graph. An edge without direction (A and B are simply connected) makes an undirected graph. Trees and linked lists are directed graphs: prev, next, left_child, right_child all point one way.

Formats: how a graph arrives in an interview

A graph is an abstract concept (an idea, not a specific object). It becomes concrete when stored in a data structure. Three formats cover almost every problem: a matrix, an adjacency matrix, and an adjacency list.

Format 1: Matrix (a 2-D grid)

A matrix is a 2-D array: a list of rows, each row a list of values. It is 0-indexed in both directions. grid[1] is the second row. grid[1][0] is the first column of the second row. Always row first, then column.

grid = [[0, 0, 0, 0],
        [1, 1, 0, 0],
        [0, 0, 0, 1],
        [0, 1, 0, 0]]

grid[1]      # [1, 1, 0, 0]  → the second row
grid[1][0]   # 1             → row 1, column 0

How is this a graph? Say every 0 is a vertex and we may move up, down, left, right between neighboring 0s. Drawing those moves as edges gives groups of connected zeros. Each group is a connected component (a set of vertices where every vertex can reach every other). Walking this graph is called matrix traversal, and it is sections 2 and 3. Space: O(n · m) for n rows and m columns.

Format 2: Adjacency matrix

A less common input format, but you must recognize it. It looks like the grid, but the meaning is different. Here the index is the vertex. adjMatrix[v1][v2] = 1 means "there is an edge from vertex v1 to vertex v2"; 0 means no edge. Row = from, column = to. The edges are directed: adjMatrix[1][2] == 0 says no edge 1 → 2, and separately adjMatrix[2][1] == 0 says no edge 2 → 1.

adjMatrix = [[0, 0, 0, 0],
             [1, 1, 0, 0],
             [0, 0, 0, 1],
             [0, 1, 0, 0]]

# an edge exists from v1 to v2
adjMatrix[v1][v2] = 1
# an edge exists from v2 to v1
adjMatrix[v2][v1] = 1
# no edge exists from v1 to v2
adjMatrix[v1][v2] = 0
# no edge exists from v2 to v1
adjMatrix[v2][v1] = 0

Format 3: Adjacency list

Typically the most common representation, and the one you will build yourself. Each vertex keeps a list of its neighbors (the vertices it has an edge to). It can be a 2-D array, but it is usually a hashmap, or a class where each node holds its own neighbor list.

# GraphNode used for adjacency list
class GraphNode:
    def __init__(self, val):
        self.val = val
        self.neighbors = []      # references to other GraphNodes

An adjacency list stores only the edges that exist, so it is more space efficient than an adjacency matrix: O(V + E). Section 4 builds one from a list of edges and traverses it.

2Matrix DFS: count the paths

DFS on a matrix works like DFS on a tree: from a position, go as deep as you can before trying the next option. The moves are up, down, left, right. Some problems also allow diagonal moves; not here.

The problem. Count the unique paths from the top-left cell to the bottom-right cell. A path may only move along 0s and cannot visit the same cell more than once.

matrix = [[0,0,0,0],
          [1,1,0,0],
          [0,0,0,1],
          [0,1,0,0]]

This is backtracking: DFS is recursive, we try every path, and when a path cannot reach the bottom right we undo the last step and try another direction. Each call returns the number of valid paths that start from its cell, and a parent adds up what its four children return.

Base cases: when to stop

Return 0 (no path through this cell) when any of these is true:

• Out of bounds. Row r or column c is negative, or equals the matrix length. Both must be valid; you cannot search matrix[-1][3].
• Already visited. This coordinate is on the current path. Revisiting would count the same path many times, or loop forever.
• Blocked. The cell holds a 1; you cannot move through 1s.

Return 1 (one path found) when you stand on the bottom-most row and right-most column: matrix[3][3] here, matrix[ROWS-1][COLS-1] in general.

The implementation

Keep a hash set visit of coordinates on the current path. A set gives O(1) insert and lookup. (A 2-D boolean array the size of the grid works too.) From (r, c), recurse on (r+1, c), (r-1, c), (r, c+1), (r, c-1). Each call returns 1 or 0; add it to count. The line that makes this backtracking: after exploring all four directions, remove the current coordinate from visit, so a different path can use this cell.

# Matrix (2D Grid)
grid = [[0, 0, 0, 0],
        [1, 1, 0, 0],
        [0, 0, 0, 1],
        [0, 1, 0, 0]]

# Count paths (backtracking)
def dfs(grid, r, c, visit):
    ROWS, COLS = len(grid), len(grid[0])
    if (min(r, c) < 0 or
        r == ROWS or c == COLS or
        (r, c) in visit or grid[r][c] == 1):
        return 0
    if r == ROWS - 1 and c == COLS - 1:
        return 1

    visit.add((r, c))

    count = 0
    count += dfs(grid, r + 1, c, visit)    # down
    count += dfs(grid, r - 1, c, visit)    # up
    count += dfs(grid, r, c + 1, visit)    # right
    count += dfs(grid, r, c - 1, visit)    # left

    visit.remove((r, c))                   # backtrack: free this cell for other paths
    return count

dfs(grid, 0, 0, set())    # → 2

The function returns 2 for this grid. The video shows it in two moves: first the DFS finds one path; then it backtracks and finds a second path that goes through matrix[0][3].

Trace: the visit set growing and shrinking

Coordinates are written as rc pairs to save space: 12 means (1, 2). The direction order is down, up, right, left, exactly as in the code. Only the important calls are shown; out-of-bounds and wall calls return 0 immediately and are summarized.

Time and space

If we only counted cells, the worst case visits every coordinate: O(n · m). But this problem counts paths, and from every coordinate there are four choices. Draw it as a decision tree: each node has at most 4 children (a branching factor of 4) and the tree can be n · m levels deep (a path can pass through every cell). That gives O(4^n·m) time in the worst case.

Space: the recursive call stack can be n · m frames deep (one per cell on the current path), and the visit set can hold n · m coordinates. Both O(n · m).

3Matrix BFS: the shortest path

BFS on a matrix is most commonly used to find the shortest path: the smallest number of moves from one cell to another. It is the same as tree BFS with two differences: more edge cases (bounds, walls, revisits) and a different setup (a start coordinate instead of a root). Four directions only.

The problem. Find the length of the shortest path from the top-left cell to the bottom-right cell of the same grid. DFS could work (find every path, keep the shortest), but BFS is more efficient because it stops the moment the target appears.

Setup

Read the grid dimensions for bounds checks. A hash set for visited vertices. A deque (double-ended queue, O(1) at both ends) to hold the vertices of the current level. Put (0, 0) in the deque and mark it visited before the loop starts.

from collections import deque

def bfs(grid):
    ROWS, COLS = len(grid), len(grid[0])
    visit = set()
    queue = deque()
    queue.append((0, 0))
    visit.add((0, 0))

The level loop

Initialize length = 0. The outer while queue runs once per level. The inner for i in range(len(queue)) pops exactly the vertices that were in the queue when the level started (the length is read once, so vertices added during the level wait for the next one). Popping gives (r, c). If it is the bottom-right cell, return length. Otherwise, instead of visiting children like a tree, visit the four neighbors.

Neighbor positions come from a directions array: neighbors = [[0, 1], [0, -1], [1, 0], [-1, 0]] = right, left, down, up. Add each direction to the current position to get the new position. The if inside is the same check as DFS: out of bounds, already visited, or a wall means continue. Otherwise append the neighbor to the queue and add it to visit immediately, at append time rather than pop time, so the same cell never sits in the queue twice.

# Shortest path from top left to bottom right
def bfs(grid):
    ROWS, COLS = len(grid), len(grid[0])
    visit = set()
    queue = deque()
    queue.append((0, 0))
    visit.add((0, 0))

    length = 0
    while queue:
        for i in range(len(queue)):          # exactly one level
            r, c = queue.popleft()
            if r == ROWS - 1 and c == COLS - 1:
                return length

            neighbors = [[0, 1], [0, -1], [1, 0], [-1, 0]]
            for dr, dc in neighbors:
                if (min(r + dr, c + dc) < 0 or
                    r + dr == ROWS or c + dc == COLS or
                    (r + dr, c + dc) in visit or grid[r + dr][c + dc] == 1):
                    continue
                queue.append((r + dr, c + dc))
                visit.add((r + dr, c + dc))     # mark when queued, not when popped
        length += 1

bfs(grid)    # → 6

Trace: level by level

The queue column shows the queue at the moment the level starts, which is exactly the set of cells at distance length. Everything appended during the level has distance length + 1.

Time and space

A coordinate is never visited twice, so each of the n · m cells is popped at most once and checks at most 4 neighbors: O(n · m) time. Space is also O(n · m): the queue and the hash set can each hold every cell. No exponential term, because BFS never re-explores a cell for a different path the way backtracking does.

4Adjacency list: build it, then DFS and BFS it

The adjacency list is probably the easiest format to traverse. Finding the neighbors of a vertex is one lookup, and there are no bounds to check because a neighbor list only contains real vertices.

Building it from a list of directed edges

Use a hashmap: key = vertex, value = list of that vertex's neighbors. A hashmap works because keys are unique, so each vertex has exactly one list. For each edge [src, dst], make sure both vertices have a key (a vertex with only incoming edges still needs an empty list), then append dst to src's list. Only src's list changes, because the edge is directed.

# GraphNode used for adjacency list
class GraphNode:
    def __init__(self, val):
        self.val = val
        self.neighbors = []

# Or use a HashMap
adjList = { "A": [], "B": [] }

# Given directed edges, build an adjacency list
edges = [["A", "B"], ["B", "C"], ["B", "E"], ["C", "E"], ["E", "D"]]

adjList = {}

for src, dst in edges:
    if src not in adjList:
        adjList[src] = []
    if dst not in adjList:
        adjList[dst] = []
    adjList[src].append(dst)

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

DFS on an adjacency list: count paths from source to target

Same backtracking shape as the matrix version, with the base cases simplified. If the node is already on the current path, return 0. If the node is the target, return 1. Otherwise add the node to visit, sum the results from every neighbor, then remove the node (backtrack) and return the sum.

# Count paths (backtracking)
def dfs(node, target, adjList, visit):
    if node in visit:
        return 0
    if node == target:
        return 1

    count = 0
    visit.add(node)
    for neighbor in adjList[node]:
        count += dfs(neighbor, target, adjList, visit)
    visit.remove(node)

    return count

dfs("A", "E", adjList, set())    # → 2   (A-B-E and A-B-C-E)

Time. Counting paths by backtracking is exponential. In the worst case every vertex connects to every other (E ≤ V²). If each vertex has N edges and the decision tree has height V, the work is N^V. In the worst case N = V, giving O(V^V). That is the honest bound for "count all paths"; do not confuse it with plain DFS reachability, which is O(V + E) because it visits each vertex once and never removes it from visit.

BFS on an adjacency list: shortest path from node to target

Shortest path here means reaching the destination through the fewest vertices (equivalently, the fewest edges). The code is matrix BFS without the edge cases: no bounds, no walls. Increase length after each level until the target is popped.

# Shortest path from node to target
def bfs(node, target, adjList):
    length = 0
    visit = set()
    visit.add(node)
    queue = deque()
    queue.append(node)

    while queue:
        for i in range(len(queue)):
            curr = queue.popleft()
            if curr == target:
                return length

            for neighbor in adjList[curr]:
                if neighbor not in visit:
                    visit.add(neighbor)
                    queue.append(neighbor)
        length += 1
    return length

bfs("A", "E", adjList)    # → 2

Time: O(V + E). In the worst case BFS visits every vertex once and looks at every edge once. This assumes a normal graph: no self loops and not the maximal V² edges, so V and E are counted separately instead of collapsing into V².

This page only scratches the surface. Weighted graphs, Dijkstra, topological sort, and union-find are in NeetCode's Advanced Algorithms course. Everything there builds on the two traversals above.

5Moves that solve most graph problems

The lessons teach two traversals on two formats. Interviews dress them up in stories about islands, oranges, courses, and mazes. These six moves cover the stories.

Move 1: The grid DFS template with a bounds check

Every grid problem starts with the same skeleton: read ROWS and COLS, write the directions array, write a nested dfs that rejects out-of-bounds, blocked, and visited cells, then loop over neighbors. A small in_bounds helper keeps the check readable.

directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]   # right, left, down, up

def in_bounds(grid, r, c):
    return 0 <= r < len(grid) and 0 <= c < len(grid[0])

def grid_dfs(grid, r, c, visit):
    if (not in_bounds(grid, r, c) or
            grid[r][c] == 1 or (r, c) in visit):
        return
    visit.add((r, c))
    for dr, dc in directions:
        grid_dfs(grid, r + dr, c + dc, visit)
    # no visit.remove here: this is reachability, not path counting

When to use: any time the input is a 2-D list and the question is about connected cells. Note the chained comparison 0 <= r < len(grid): it is the Python idiom for "in range" and it catches the negative-index trap in one expression.

Move 2: Flood fill and Number of Islands

An island is a connected component of land cells. To count them, scan every cell with two nested loops. When you find land that is not yet visited, you have discovered a new island: run DFS from it to mark the whole component, and add 1 to the count. The DFS is called a flood fill because it spreads like water until it hits the edge of the component.

def num_islands(grid):                 # LeetCode 200: cells are "1" (land) or "0" (water)
    ROWS, COLS = len(grid), len(grid[0])
    visit = set()

    def dfs(r, c):
        if (r < 0 or c < 0 or r >= ROWS or c >= COLS or
                grid[r][c] != "1" or (r, c) in visit):
            return
        visit.add((r, c))
        for dr, dc in directions:
            dfs(r + dr, c + dc)

    count = 0
    for r in range(ROWS):
        for c in range(COLS):
            if grid[r][c] == "1" and (r, c) not in visit:
                dfs(r, c)                  # floods the whole island
                count += 1
    return count


def max_area(grid):                    # LeetCode 695: same shape, dfs returns a size
    ROWS, COLS = len(grid), len(grid[0])
    visit = set()

    def dfs(r, c):
        if (r < 0 or c < 0 or r >= ROWS or c >= COLS or
                grid[r][c] == 0 or (r, c) in visit):
            return 0
        visit.add((r, c))
        return 1 + sum(dfs(r + dr, c + dc) for dr, dc in directions)

    return max((dfs(r, c) for r in range(ROWS) for c in range(COLS)), default=0)


def flood_fill(image, sr, sc, color):  # LeetCode 733: recolor one component
    ROWS, COLS = len(image), len(image[0])
    old = image[sr][sc]
    if old == color:
        return image                   # already that color: recoloring would never stop

    def dfs(r, c):
        if r < 0 or c < 0 or r >= ROWS or c >= COLS or image[r][c] != old:
            return
        image[r][c] = color            # the new color doubles as the visited mark
        for dr, dc in directions:
            dfs(r + dr, c + dc)

    dfs(sr, sc)
    return image

When to use: "count the regions", "size of the largest region", "recolor a region", "is this region enclosed". The outer double loop plus an inner flood fill is the whole idea. Total time O(n · m): each cell is visited by the scan once and by at most one DFS.

Move 3: BFS shortest path with the level loop

Any "minimum number of steps" question on an unweighted graph is BFS. Keep the level loop, mark at append time, and return -1 after the loop for "unreachable". For problems with many starting points (Rotting Oranges, Walls and Gates) put all of them in the queue before the loop starts: this is a multi-source BFS, and it costs nothing extra.

def shortest_path(grid, start, target):
    ROWS, COLS = len(grid), len(grid[0])
    queue = deque([start])
    visit = {start}
    length = 0
    while queue:
        for _ in range(len(queue)):        # one level = one unit of distance
            r, c = queue.popleft()
            if (r, c) == target:
                return length
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if (0 <= nr < ROWS and 0 <= nc < COLS and
                        grid[nr][nc] == 0 and (nr, nc) not in visit):
                    visit.add((nr, nc))
                    queue.append((nr, nc))
        length += 1
    return -1                                # never reached the target


def rotting_oranges(grid):               # LeetCode 994: multi-source BFS
    ROWS, COLS = len(grid), len(grid[0])
    queue = deque()
    fresh = 0
    for r in range(ROWS):
        for c in range(COLS):
            if grid[r][c] == 2:
                queue.append((r, c))         # every rotten orange is a source
            elif grid[r][c] == 1:
                fresh += 1
    minutes = 0
    while queue and fresh:
        for _ in range(len(queue)):
            r, c = queue.popleft()
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if 0 <= nr < ROWS and 0 <= nc < COLS and grid[nr][nc] == 1:
                    grid[nr][nc] = 2            # marking in place = visited
                    fresh -= 1
                    queue.append((nr, nc))
        minutes += 1
    return minutes if fresh == 0 else -1

When to use: the words "shortest", "minimum steps", "nearest", "how many minutes until". If edges have different weights, BFS is wrong and you need Dijkstra (advanced course).

Move 4: Building adjacency lists from edge lists

LeetCode rarely hands you an adjacency list. It hands you n and edges. The first thing you write is the build loop. collections.defaultdict(list) removes the "if key not in dict" lines. For an undirected graph, add the edge in both directions. For numeric vertices 0..n-1, a list of lists is faster than a dict.

from collections import defaultdict

def build_directed(edges):
    adj = defaultdict(list)
    for src, dst in edges:
        adj[src].append(dst)
        adj[dst]                       # touch it so a pure sink like D still gets a key
    return adj

def build_undirected(edges):
    adj = defaultdict(list)
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)               # both directions: each edge stored twice
    return adj

def build_undirected_list(n, edges):  # vertices are 0 .. n-1
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
    return adj

build_undirected_list(3, [[0, 1], [1, 2]])    # → [[1], [0, 2], [1]]

When to use: every adjacency-list problem, first five lines. Ask the interviewer "directed or undirected?" before writing the loop. Sum of all list lengths is E for directed, 2E for undirected.

Move 5: Visited set vs marking the grid in place

A visit set is the safe default: it works for any format, never damages the input, and is required when you must backtrack (remove) or when the grid is read-only. Marking in place (overwriting a visited land cell with "0", or a fresh orange with 2) saves the O(n · m) set and one lookup per cell, but it destroys the input. Say which one you are choosing and why.

def num_islands_in_place(grid):
    ROWS, COLS = len(grid), len(grid[0])

    def sink(r, c):
        if r < 0 or c < 0 or r >= ROWS or c >= COLS or grid[r][c] != "1":
            return
        grid[r][c] = "0"                 # the grid itself is the visit set
        for dr, dc in directions:
            sink(r + dr, c + dc)

    count = 0
    for r in range(ROWS):
        for c in range(COLS):
            if grid[r][c] == "1":
                sink(r, c)
                count += 1
    return count                       # grid is now all "0"

Move 6: DFS for reachability and counting, BFS for shortest path

The choice is usually decided by one word in the problem statement.

def has_path(adj, src, dst, visit=None):     # LeetCode 1971 shape: reachability, no backtracking
    if visit is None:
        visit = set()
    if src == dst:
        return True
    visit.add(src)
    for nb in adj[src]:
        if nb not in visit and has_path(adj, nb, dst, visit):
            return True
    return False


def count_components(n, edges):            # NeetCode 323 shape: islands, but on an adjacency list
    adj = build_undirected_list(n, edges)
    visit = set()

    def dfs(node):
        visit.add(node)
        for nb in adj[node]:
            if nb not in visit:
                dfs(nb)

    count = 0
    for node in range(n):
        if node not in visit:
            dfs(node)
            count += 1
    return count

count_components(5, [[0, 1], [1, 2], [3, 4]])    # → 2

6Big-O summary

n and m are grid dimensions; V and E are vertex and edge counts. Say the assumption behind each bound out loud: "each cell visited once" or "each vertex and each edge once".

* The V^V bound assumes the densest possible graph. On a grid the same idea gives 4^n·m because the branching factor is fixed at 4. Both are "count every path" bounds; the moment you stop removing from visit, the exponent disappears and you are back to V + E.

7Mistakes to watch for

8Practice, in this order

Do them with no notes open. After each one, check your bounds check, your visited marking, and your choice of DFS or BFS against the moves in section 5.

Your next step today: LeetCode 200, Number of Islands. Write it with a visited set first, then rewrite it marking in place, and compare the two against Move 5.

9Self-check

Answer out loud before opening. If you cannot answer in one breath, reread that section.