DSA sheet · Graphs · Patterns overview

Graph Patterns Overview

This video is the map of the whole graph topic. The teacher's message: graphs sound hard, but if you already know BFS and DFS from trees, most of the work is done. She splits every graph question into three families: traversal (BFS, DFS), ordering (topological sort) and shortest path (Dijkstra, Bellman-Ford, Floyd-Warshall), and gives the words in the question that tell you which family you're in. Each pattern below gets its idea, the clue words, a tiny example, a Python template, a dry run and its cost, so you can recognise it before you've seen the problem.

This is a concept video, so the 9 steps are adapted:
what a graph is → why we need it → how to store it (with code) → each pattern: idea, clue words, tiny example, template, dry run, cost → which problems belong to which pattern → remember

• Part 0 · What a graph is, and how it differs from a tree
• Part A · Storing a graph: grids vs adjacency lists
• Part B · Traversal pattern 1: BFS
• Part C · Traversal pattern 2: DFS
• Part D · Ordering pattern: topological sort
• Part E · Shortest path patterns: Dijkstra, Bellman-Ford, Floyd-Warshall
• Part F · Which problem belongs to which pattern
• Part G · Revision page

Part 0 · What a graph is

1Nodes, edges, and the three kinds of edges

A graph is a bunch of nodes (also called vertices; count V) joined by edges (count E). Nodes may be linked so that they form a cycle: a way to walk around and come back to where you started.

• Undirected edge (1)—(2): walk it both ways.
• Directed edge (1)→(2): only from 1 to 2.
• Weighted edge (1)—4—(2): walking it costs 4. With no number, the cost is 1.

Problem 2 goes through every term (cycles, weights, in-degree, components…) in detail.

2Is a tree a graph? Yes, but a graph is more general

A tree is a graph too: nodes joined by edges. The teacher lists three differences:

(8)—(2)—(1)—(3)—(7)—(9)
            /   \
          (4)   (6)
            \   /
             (5)

from 3 to 5:  3 → 4 → 5   or   3 → 6 → 5   (two routes, and a cycle 3-4-5-6-3)

3Why we need graphs

Many real things are networks, not hierarchies: computer networks, Google Maps roads and highways, people who know each other, tasks that depend on other tasks. A tree can't hold them, because things link sideways, in loops, and from several sides. Wherever relationships, paths or dependencies matter, think graph.

Part A · Storing a graph

To walk through a graph we keep asking: "I'm at node x; which nodes can I go to next?" (its neighbours, which she calls children). How we answer that depends on how the graph is given.

1Case 1: a grid (matrix of cells)

If the input is a grid and you stand on a cell, the question says where you may move: up, down, left, right. The next cells come from the direction, so there's nothing to store. From (i, j) the neighbours are (i−1, j), (i+1, j), (i, j−1), (i, j+1), as long as they're inside the grid.

DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]      # up, down, left, right

def grid_neighbours(grid, i, j):
    rows, cols = len(grid), len(grid[0])
    for dr, dc in DIRS:
        r, c = i + dr, j + dc
        if 0 <= r < rows and 0 <= c < cols:    # stay inside the grid
            yield r, c

2Case 2: nodes and edges → build an adjacency list

Otherwise the question lists the edges as pairs: [1, 2], [1, 3], [2, 8], [3, 4], … To find 1's children you'd have to scan the whole list. Here the pairs happen to be sorted, but if [1, 3] sat at the very end you'd still need a full scan: O(E) per node, so O(n²) over all nodes, just to find children.

The fix: scan the list once and file every pair into a hash map (a dict): key = node, value = list of its children. For a pair [left, right], put right into left's list. After that, 1's children are just adj[1], all packed together.

from collections import defaultdict

def build_adj(edges, directed=False):
    adj = defaultdict(list)          # node -> list of children
    for u, v in edges:
        adj[u].append(v)             # the left node gets the right one as a child
        if not directed:
            adj[v].append(u)         # undirected: the other way too
    return adj

Her example: edges = [[1,2],[1,3],[2,8],[3,4],[3,6],[3,7],[4,5],[5,6],[7,9]]. In the video she files each pair one way only (1 → [2, 3], 2 → [8], 3 → [4, 6, 7], 4 → [5], 5 → [6], 7 → [9]), which is directed=True. For an undirected graph, like the picture in Part 0, both directions go in, so 3 → [1, 4, 6, 7].

Part B · Traversal pattern 1: BFS

1The idea

Breadth First Search: from the start, expand all neighbours at once, then all of their new neighbours, and so on, level by level. Standing at 3, BFS reaches 7, 6, 4 and 1 "in the first second". It's the same BFS as in trees, with a queue deciding what comes next.

2Clue words → BFS

• "shortest path" (when every edge costs the same)
• "minimum number of steps" / "minimum moves" to reach a node
• "nearest" node / cell
• "level-wise" traversal

The teacher says that with these words you can go for BFS straight away. The reason: BFS finishes everything at distance 1 before distance 2, so the first time it reaches a node is along the fewest edges.

3Template

from collections import deque

def bfs_dist(adj, src, n):
    dist = [-1] * n                  # -1 = not reached yet (doubles as visited)
    dist[src] = 0
    queue = deque([src])
    while queue:
        x = queue.popleft()          # oldest first = level by level
        for y in adj[x]:
            if dist[y] == -1:        # first time we see y = shortest way
                dist[y] = dist[x] + 1
                queue.append(y)
    return dist

4Dry run from 3 (undirected Part 0 graph)

Note 5 gets distance 2 the first time it's found (via 4); finding it again via 6 changes nothing. Cost: O(V + E) time, O(V) space. The full step-by-step version is Problem 3.

Part C · Traversal pattern 2: DFS

1The idea

Depth First Search: from 3, step to the first child, 7. Now you may not go to 3's other children (1, 4, 6) yet. You're at 7, so only 7's unvisited children count: go to 9. You keep going deeper until you're stuck, then backtrack (step back) and only then try 3's next child. In code it's recursion (or an explicit stack).

2Clue words → DFS

• "explore all paths" / "print all paths": from 3, the paths are 3 → 7 → 9, then 3 → 6 → 5 → 4 (back next to 3), then the next…
• "check connectivity": are these two nodes connected? are all nodes reachable?
• "detect a cycle"
• "go deep before backtracking": finish one branch fully before starting the next.

3Templates

def all_paths(adj, src, dst):
    paths, path, on_path = [], [src], {src}
    def dfs(x):
        if x == dst:
            paths.append(path[:])          # copy the finished path
            return
        for y in adj[x]:
            if y not in on_path:           # don't loop around inside one path
                on_path.add(y); path.append(y)
                dfs(y)                     # go deep
                path.pop(); on_path.remove(y)   # backtrack, so other paths can use y
    dfs(src)
    return paths

def connected(adj, a, b):
    seen = {a}
    def dfs(x):
        for y in adj[x]:
            if y not in seen:
                seen.add(y)
                dfs(y)
    dfs(a)
    return b in seen

def has_cycle_undirected(adj, nodes):
    seen = set()
    def dfs(x, parent):
        seen.add(x)
        for y in adj[x]:
            if y == parent:
                continue                   # the edge we just came along
            if y in seen or dfs(y, x):
                return True                # reached an old node another way
        return False
    return any(x not in seen and dfs(x, None) for x in nodes)

4Dry run: all paths from 3 to 5

1. dfs(3): children 1, 4, 6, 7. Go to 1 → 1's only new child is 2 → 2 leads to 8 → 8 is a dead end. Back off all the way to 3 (1, 2, 8 are un-marked as we leave).
2. 3 → 4 → 5 = target → save [3, 4, 5]. Step back to 4; 4 has nothing else. Back to 3.
3. 3 → 6 → 5 = target → save [3, 6, 5]. (5 was freed when we left it in step 2.)
4. 3 → 7 → 9: dead end. Done: [[3, 4, 5], [3, 6, 5]].

Costs: connected and has_cycle_undirected are O(V + E). all_paths can be exponential, because the number of paths itself can be.

Part D · Ordering pattern: topological sort

1Clue words

• "prerequisites", "dependency": a task can't start until another is finished
• "ordering", "scheduling": do this first, then that

When the order is fixed by rules like these, use topological sort (an order where every task comes after everything it depends on). Famous problems: Course Schedule I and II.

2Her example

To take course A you must finish B. To take C you must also finish B.

       (B)
      ↙   ↘
    (C)   (A)        B must come first; A and C wait for it

She keeps two lists:

• dependency count (= in-degree, the number of arrows coming in): A → 1, B → 0, C → 1.
• children (an adjacency list of "who is waiting for me"): B → [C, A].

3How it runs (Kahn's algorithm)

1. Push every node with in-degree 0 into a queue. These are free to take right now. Here: B.
2. Pop B (take it). Visit its children: C's count 1 → 0, so push C. A's count 1 → 0, so push A.
3. Pop C (no children). Pop A (no children). The queue is empty.
4. Order taken: B, C, A. If some nodes never reached 0, there's a cycle and no valid order exists.

from collections import deque

def topo_sort(nodes, needs):            # needs = [(task, prerequisite), ...]
    children = {x: [] for x in nodes}
    indeg = {x: 0 for x in nodes}
    for task, pre in needs:
        children[pre].append(task)      # pre finishing releases task
        indeg[task] += 1
    queue = deque(x for x in nodes if indeg[x] == 0)   # free right now
    order = []
    while queue:
        x = queue.popleft()
        order.append(x)
        for c in children[x]:
            indeg[c] -= 1
            if indeg[c] == 0:           # its last prerequisite is done
                queue.append(c)
    return order if len(order) == len(nodes) else None   # None = cycle

topo_sort(["A", "B", "C"], [("C", "B"), ("A", "B")]) → ['B', 'C', 'A']. (C is listed first, so B's children list is [C, A] as in her drawing; the order inside the queue follows that list.) Cost: O(V + E).

Part E · Shortest path patterns

1The question type

"From node A to node B, what's the cheapest total cost?" There may be many paths, and each edge has a weight. Plain BFS counts edges, not costs, so a path with more but cheaper edges can beat it. We need algorithms that add up weights. Which one depends on two questions:

2Dijkstra: always expand the cheapest known node

From the current node there may be several options. We want to continue from the cheapest one first, and a priority queue (in Python, heapq, a min-heap) always hands us the smallest distance found so far. Works only when all weights are positive (or zero).

import heapq

def dijkstra(adj, src, n):              # adj[u] = [(v, w), ...], all w >= 0
    INF = float('inf')
    dist = [INF] * n
    dist[src] = 0
    heap = [(0, src)]                   # (distance so far, node)
    while heap:
        d, u = heapq.heappop(heap)      # the cheapest node not yet finished
        if d > dist[u]:
            continue                    # an old, outdated entry: skip
        for v, w in adj[u]:
            if d + w < dist[v]:         # found a cheaper way to v
                dist[v] = d + w
                heapq.heappush(heap, (dist[v], v))
    return dist

 (0) ——4——→ (1) ——1——→ (3)
  |          ↑           ↑
  1          2           5
  ↓          |           |
 (2) ————————┴———————————┘

Directed edges: 0→1 (4), 0→2 (1), 2→1 (2), 1→3 (1), 2→3 (5).

3Bellman-Ford: negative weights and negative cycles

A negative cycle is a loop whose weights add up below zero. Her picture: going 1 → 2 → 5 → back to 1 with weights −2, −3 (and 0) totals −5, so every extra lap is cheaper and "shortest" stops making sense. Bellman-Ford handles negative edges and can report such a cycle.

Idea: a shortest path (with no negative cycle) uses at most V − 1 edges. So relax every edge (try "is going through this edge cheaper?") V − 1 times. Then try one more round: if anything still improves, a negative cycle exists.

def bellman_ford(n, edges, src):        # edges = [(u, v, w), ...]
    INF = float('inf')
    dist = [INF] * n
    dist[src] = 0
    for _ in range(n - 1):              # a shortest path has at most n-1 edges
        changed = False
        for u, v, w in edges:
            if dist[u] != INF and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                changed = True
        if not changed:
            break                       # nothing moved: already final
    for u, v, w in edges:               # one extra round
        if dist[u] != INF and dist[u] + w < dist[v]:
            return None                 # still improving -> negative cycle
    return dist

Dry run on 0→1 (1), 0→2 (3), 2→1 (−3), edges in that order. Round 1: dist[1] = 1, dist[2] = 3, then via 2: dist[1] = 0. Round 2: nothing changes → stop. Extra check: nothing improves → no negative cycle. dist = [0, 0, 3], the answer Dijkstra got wrong. Cost: O(V · E).

4Floyd-Warshall: every node to every node

When the question wants the shortest distance between all pairs, keep a V × V table d. For each node k in turn, allow k as a stop in the middle: d[i][j] = min(d[i][j], d[i][k] + d[k][j]). After all k, every pair is final. Negative edges are fine; a negative number on the diagonal (d[i][i] < 0) means a negative cycle.

def floyd_warshall(n, edges):           # edges = [(u, v, w), ...]
    INF = float('inf')
    d = [[0 if i == j else INF for j in range(n)] for i in range(n)]
    for u, v, w in edges:
        d[u][v] = min(d[u][v], w)
    for k in range(n):                  # allow k as a middle stop
        for i in range(n):
            for j in range(n):
                if d[i][k] + d[k][j] < d[i][j]:
                    d[i][j] = d[i][k] + d[k][j]
    return d                            # d[i][i] < 0  ->  negative cycle

On the Dijkstra graph, row 0 of the result is [0, 3, 1, 4], the same as Dijkstra's answer, and the other rows come for free. Cost: O(V³) time, O(V²) space, so only for small V (a few hundred).

Part F · Which problem belongs to which pattern

The teacher has grouped the sheet's problems by pattern. Here's where each problem of this notebook sits:

Several problems can be solved with either BFS or DFS (islands, provinces, flood fill, bipartite). The table puts each under the one used first in its video.

Part G · Revision page

edges = [[1,2],[1,3],[2,8],[3,4],[3,6],[3,7],[4,5],[5,6],[7,9]]
adj = build_adj(edges)
print(sorted(adj[3]))                       # [1, 4, 6, 7]
print(bfs_dist(adj, 3, 10)[8])              # 3
print(all_paths(adj, 3, 5))                 # [[3, 4, 5], [3, 6, 5]]
print(connected(adj, 8, 9))                 # True
print(has_cycle_undirected(adj, range(1, 10)))   # True
print(topo_sort(["A", "B", "C"], [("C", "B"), ("A", "B")]))   # ['B', 'C', 'A']
wadj = [[(1, 4), (2, 1)], [(3, 1)], [(1, 2), (3, 5)], []]
print(dijkstra(wadj, 0, 4))                 # [0, 3, 1, 4]
print(bellman_ford(3, [(0, 1, 1), (0, 2, 3), (2, 1, -3)], 0))   # [0, 0, 3]
print(bellman_ford(3, [(0, 1, -2), (1, 2, -3), (2, 0, 0)], 0))  # None
print(floyd_warshall(3, [(0, 1, 1), (0, 2, 3), (2, 1, -3)])[0])  # [0, 0, 3]

Based on this video: Graph Patterns for Coding Interviews