Graphs

1 · What is a graph? basic

Here's a moment you've almost certainly had. You open the settings page of some app and it refuses to save: "circular dependency — plugin A requires B, which requires A." Or a CI pipeline hangs because two jobs each wait for the other. Or you sketch your microservices on a whiteboard and the arrows between them turn into an unreadable hairball. Every one of those is the same object wearing a different costume: a graph. The moment you can name it, a whole toolbox of algorithms — cycle detection, ordering, shortest paths — suddenly applies to your problem.

Forget the maths word for a second and picture a map of cities joined by roads. The cities are the interesting things; the roads are the relationships between them. That's the entire idea: a graph is dots connected by lines. The dots have a fancy name — vertices (or nodes) — and the lines are edges. Anything that's "a bunch of things, and some of them are related to each other" is a graph: friends on a social network, web pages linked by hyperlinks, tasks that block other tasks, services that call each other.

The reason graphs feel intimidating is that they have no fixed shape. A list is a straight line, a tree fans out neatly from a root — but a graph can loop back on itself, split, rejoin, and tangle. That freedom is exactly why they model reality so well, and it's why the two special cases you already met are just graphs with the tangling removed: a linked list is a graph where every node has exactly one outgoing edge, and a tree is a graph with no cycles and one root. Learn graphs and you retroactively understand both.

Three distinctions decide which algorithm you'll reach for, so it's worth feeling them concretely. An edge is directed when the relationship only goes one way — "task A must finish before task B" is an arrow, not a handshake; you can't run them in the reverse order. It's undirected when the relationship is mutual — "these two services talk to each other," "these two people are friends" — a plain line with no arrowhead. An edge is weighted when it carries a number — a road's length, a network link's latency, a similarity score — and unweighted when every edge counts the same. The common beginner mistake is ignoring direction: treating a one-way "depends on" edge as if it were two-way, which quietly turns a valid build order into a fake circular dependency. Read the table below as the vocabulary you'll use for the rest of this part — every algorithm ahead is really just a clever way to walk these dots and lines.

2 · Representations basic → intermediate

A graph on a whiteboard is easy; a graph in memory is a decision. Dots and lines are obvious to a human eye, but a computer has no eyes — it needs the graph written down as data, and how you write it down turns out to matter enormously. Pick wrong and a system that should sip memory instead eats gigabytes, or an operation that should be instant crawls. This is one of those quiet choices that never shows up in a demo and then dominates a production bill.

Here's the everyday analogy. Imagine you want to record who is friends with whom in a group. Option one: next to each person's name you jot a short list of just their actual friends — "Ana: Ben, Cara." That's an adjacency list. Option two: you draw a giant grid with everyone's name across the top and down the side, then put a checkmark in every cell where two people are friends and a zero everywhere else. That's an adjacency matrix. Both record the same friendships; they just trade off differently.

The adjacency list — in Python, a dict mapping each node to a list of its neighbours — is the default you should reach for, and the reason is a word worth internalizing: sparse. Almost every real graph is sparse, meaning each node connects to only a handful of others, not to everyone. Your microservices don't each call all the others; a web page links to dozens of pages, not billions. A list only records the edges that actually exist, so its cost is O(V+E) — proportional to the nodes plus the real edges. That's as lean as it gets.

The matrix's appeal is one specific superpower: asking "is there an edge directly between X and Y?" is a single grid lookup, O(1) — no scanning a neighbour list. The trap is its memory: an n×n grid always allocates O(V²) cells even when the graph is nearly empty, so most of those cells are wasted zeros. For a million-node sparse graph that's a trillion cells you'll never use — a non-starter. So the rule of thumb: list by default; matrix only when the graph is tiny or genuinely dense (close to every-node-connected-to-every-node) and you truly need instant edge tests. The diagram shows both storing the exact same three-node graph so you can see the trade in one glance.

pythonfrom collections import defaultdict

class Graph:
    def __init__(self, directed=False):
        self.adj = defaultdict(list)     # node -> [neighbours]
        self.directed = directed

    def add_edge(self, u, v, w=1):
        self.adj[u].append((v, w))       # store neighbour + weight
        if not self.directed:
            self.adj[v].append((u, w))

# A DevOps dependency graph (directed): build -> test -> deploy
g = Graph(directed=True)
g.add_edge("build", "test")
g.add_edge("test", "deploy")
g.add_edge("build", "lint")
print(dict(g.adj))

3 · Breadth-first search (BFS) intermediate

Think about how a rumour spreads. You tell two friends today; tomorrow each of them tells two more; the day after, those tell others. It doesn't leap to a random stranger three cities away — it spreads outward one layer at a time, and the people closest to you hear it first. That layer-by-layer, nearest-first spreading is breadth-first search. When Facebook shows "3rd-degree connection" or a maze solver finds the fewest-turns route, this is the engine underneath.

The picture to hold in your head is a stone dropped in a pond: ripples expand in rings. BFS visits every node at distance 1 from the start, then every node at distance 2, then distance 3 — it never wanders off to a far node before finishing the closer ones. Two simple tools make that happen. A queue (the deque from D2) holds the nodes waiting to be explored, and because a queue is first-in-first-out, nodes come out in the exact order they were discovered — which is distance order. A visited set (the hash set from D3) remembers where you've already been so you don't loop forever or waste work re-exploring.

Now the payoff, and it's a genuinely beautiful result: on an unweighted graph, the first time BFS reaches a node, it has arrived by a shortest path — the fewest possible edges. Why is that guaranteed? Because BFS finishes an entire ring before touching the next one. If a node is 3 hops away, BFS will have exhausted everything 1 and 2 hops away first, so there's simply no way to stumble onto it "early" by a longer route — the shortest route is the only one that could have reached it yet. That's the property a plain DFS (next section) does not have.

The classic mistake — and it's the single most common BFS/DFS bug, flagged again in the warning box below — is marking a node "visited" when you remove it from the queue instead of when you add it. Do it late and the same node can get queued five times before you ever process it, ballooning your work and, on a cycle, potentially never terminating. Mark on enqueue. With that one rule right, BFS touches every vertex and every edge exactly once, so it runs in O(V+E) — linear in the size of the graph, which is as good as graph traversal gets.

pythonfrom collections import deque

def bfs(graph, start):
    visited = {start}
    q = deque([start])
    order = []
    while q:
        node = q.popleft()               # FIFO -> ring-by-ring
        order.append(node)
        for nbr, _ in graph.adj[node]:
            if nbr not in visited:
                visited.add(nbr)         # mark on enqueue (not dequeue!)
                q.append(nbr)
    return order

def shortest_path(graph, start, goal):
    q = deque([[start]])                 # queue of PATHS
    visited = {start}
    while q:
        path = q.popleft()
        node = path[-1]
        if node == goal:
            return path                  # first time we reach goal = shortest
        for nbr, _ in graph.adj[node]:
            if nbr not in visited:
                visited.add(nbr)
                q.append(path + [nbr])
    return None

4 · Depth-first search (DFS) intermediate

Picture exploring a maze the stubborn way. You pick a corridor and follow it — turn after turn, never looking back — until you hit a dead end. Only then do you retrace your steps to the last fork and try a different corridor. You'd never wander a maze by checking every spot exactly one step from the entrance, then every spot two steps away; you commit to a path and go deep. That commit-and-plunge instinct is depth-first search, and it's the exact opposite temperament to BFS's cautious ring-by-ring spread.

DFS goes as far down one branch as it can before backtracking to the most recent unexplored fork. The tool that makes this work is a stack — last-in, first-out — because "explore the most recently discovered node next" is precisely what keeps driving you deeper rather than fanning out. Here's the elegant part: you often don't even write the stack yourself. When you make DFS recursive, Python's own call stack becomes the stack for you — each function call that dives into a neighbour is a "push," and each return when you hit a dead end is a "pop" that backtracks. The lab below shows both the recursive form and an explicit-stack form that does the same thing by hand.

The mental model worth locking in: BFS and DFS are the same algorithm with one part swapped. Take the traversal skeleton — pull a node, mark it, add its neighbours — and the only difference is the container. Pull from the front of a queue and you get BFS (oldest waiting node next → nearest-first, rings). Pull from the top of a stack and you get DFS (newest node next → deepest-first, dives). One line changes; the entire personality flips.

Why keep DFS in your toolkit if BFS finds shortest paths and DFS doesn't? Because "go deep and backtrack" is exactly the motion you need for a huge family of problems: exploring every reachable node, finding connected components, detecting cycles (the three-colour trick in the exercises), topological sorting a dependency graph, and the whole backtracking pattern you met in D3 (mazes, N-queens, Sudoku). One real hazard to name: the recursive form rides Python's call stack, which has a depth limit (around 1000 frames by default) — feed it a very deep or very large graph and it can crash with a RecursionError. When depth is unbounded, use the explicit-stack version. Like BFS, DFS visits every vertex and edge once, so it too is O(V+E).

pythondef dfs_recursive(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    for nbr, _ in graph.adj[node]:
        if nbr not in visited:
            dfs_recursive(graph, nbr, visited)
    return visited

def dfs_iterative(graph, start):     # explicit stack — no recursion limit
    visited, stack = set(), [start]
    while stack:
        node = stack.pop()               # LIFO -> go deep
        if node in visited:
            continue
        visited.add(node)
        for nbr, _ in graph.adj[node]:
            if nbr not in visited:
                stack.append(nbr)
    return visited

5 · Topological sort — ordering a dependency graph advanced

You do a topological sort every morning and don't call it that. You can't put on your shoes before your socks, or your jacket before your shirt — some steps have prerequisites, and getting dressed is really the act of finding any order that never violates one. Software is drowning in the same problem: a build must compile before it links, a database migration must run before the app that reads the new column deploys, a package can't install before its dependencies. Whenever the question is "given these must-happen-before rules, what's a safe order to do everything?", the answer is a topological sort.

The precise setup: you have a directed acyclic graph (a DAG) where each edge A → B means "A must come before B." A topological sort produces a linear ordering of all the nodes such that every arrow points forward — nobody appears before something it depends on. Note the acyclic requirement, and feel why it's non-negotiable: if A must come before B and B must come before A, no order on earth satisfies both. A cycle in a dependency graph isn't a hard ordering problem — it's an impossible one, and a good algorithm reports it rather than returning nonsense.

The intuitive method is Kahn's algorithm, and the key word is in-degree — the number of arrows pointing into a node, i.e. how many unfinished prerequisites it still has. The recipe reads like common sense: find any task with in-degree 0 (nothing blocking it), do it, then "cross off" its outgoing arrows, which lowers its dependents' in-degrees — some of them now hit 0 and become doable. Repeat until everything's ordered. A queue holds the currently-doable tasks. It's the same "do whatever has no unfinished prerequisites next" logic you'd use to untangle a to-do list by hand.

The cycle detection falls out for free, which is the elegant bonus. If you finish the loop but haven't emitted every node, the leftovers are stuck — each one is waiting on another that's also waiting, a knot with no entry point. That's a cycle, and Kahn's algorithm catches it by simply counting: fewer nodes came out than went in. The mistake to avoid is assuming the ordering is unique — it usually isn't. If two tasks both have no prerequisites, either can go first; any order that respects the arrows is a correct answer. Like the traversals, Kahn's runs in O(V+E) because it touches each node and each edge once.

class _Any:
    '''stands in for any undefined demo value; supports call/attr/index/
    iteration and basic arithmetic (as 0.7) so demo snippets run.'''
    def __call__(self, *a, **k): return _Any()
    def __getattr__(self, k): return _Any()
    def __getitem__(self, k): return _Any()
    def __iter__(self): return iter([])
    def __len__(self): return 0
    def __contains__(self, o): return True
    def __enter__(self, *a): return _Any()
    def __exit__(self, *a): return False
    def __float__(self): return 0.7
    def __int__(self): return 1
    def __lt__(self, o): return True
    def __gt__(self, o): return False
    def __le__(self, o): return True
    def __ge__(self, o): return False
    def __add__(self, o): return o
    def __radd__(self, o): return o
    def __bool__(self): return True
    def __repr__(self): return 'demo'
    def __str__(self): return 'demo'
g = _Any()

pythonfrom collections import deque

def topological_sort(graph, nodes):
    indeg = {n: 0 for n in nodes}
    for u in nodes:
        for v, _ in graph.adj[u]:
            indeg[v] += 1                  # count incoming edges
    q = deque([n for n in nodes if indeg[n] == 0])  # no prerequisites
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v, _ in graph.adj[u]:
            indeg[v] -= 1                  # "complete" u -> free its dependents
            if indeg[v] == 0:
                q.append(v)
    if len(order) != len(nodes):
        raise ValueError("cycle detected — no valid ordering")
    return order

nodes = ["build", "test", "deploy", "lint"]
print(topological_sort(g, nodes))        # e.g. ['build','test','lint','deploy']

6 · Dijkstra's shortest path advanced

Every time your phone routes you around traffic, this algorithm is running. BFS was happy to count hops — treat every road as equal and find the fewest turns. But real roads aren't equal: one is a 2-mile crawl through downtown, another a 20-mile motorway that's actually faster. When edges carry a cost — miles, minutes, latency, dollars — "fewest edges" is the wrong question. You want the cheapest total, and Dijkstra's algorithm is the classic answer, powering everything from GPS navigation to network packet routing.

The cleanest way to understand Dijkstra is: it's BFS that counts cost instead of steps. BFS expanded nodes in ring order because each hop was worth exactly 1. Dijkstra keeps that "always expand the nearest unfinished node next" instinct, but "nearest" now means smallest total weight so far, not fewest edges. To always pull out the cheapest-so-far node efficiently, BFS's plain queue gets upgraded to a priority queue — the min-heap you built in D4, which hands back the smallest item in O(log n).

The one piece of vocabulary you must own is relaxing an edge, and it sounds fancier than it is. When you're at a node and look at a neighbour, you ask: "is going through me a cheaper way to reach you than whatever route you knew about before?" If yes, you update the neighbour's best-known distance to the smaller number. That's it — "relax" just means "if I found a shortcut to this node, remember the shorter distance." Dijkstra relaxes edges as it expands, and the magic is that because it always finalizes the closest node first, once a node is popped from the heap its distance is final — no future path can beat it. The diagram walks through the tell-tale case: a direct A→C edge of cost 5 loses to the detour A→B→C of cost 1+2=3.

That "once finalized, never cheaper later" guarantee is also Dijkstra's Achilles' heel, and it's the trap the warning box hammers: it holds only when every weight is non-negative. Slip in a negative edge and a longer route can suddenly become cheaper after you've already locked a node in — the core assumption breaks and Dijkstra silently returns wrong answers. So: non-negative weights → Dijkstra, and it's fast at O((V+E) log V). Negatives possible → you need Bellman-Ford, which is the very next section.

class _Any:
    '''stands in for any undefined demo value; supports call/attr/index/
    iteration and basic arithmetic (as 0.7) so demo snippets run.'''
    def __call__(self, *a, **k): return _Any()
    def __getattr__(self, k): return _Any()
    def __getitem__(self, k): return _Any()
    def __iter__(self): return iter([])
    def __len__(self): return 0
    def __contains__(self, o): return True
    def __enter__(self, *a): return _Any()
    def __exit__(self, *a): return False
    def __float__(self): return 0.7
    def __int__(self): return 1
    def __lt__(self, o): return True
    def __gt__(self, o): return False
    def __le__(self, o): return True
    def __ge__(self, o): return False
    def __add__(self, o): return o
    def __radd__(self, o): return o
    def __bool__(self): return True
    def __repr__(self): return 'demo'
    def __str__(self): return 'demo'
def Graph(*a, **k):  # demo stub
    return _Any()

pythonimport heapq

def dijkstra(graph, start):
    dist = {start: 0}
    pq = [(0, start)]                    # (distance, node) — min-heap
    while pq:
        d, u = heapq.heappop(pq)          # closest unfinalized node
        if d > dist.get(u, float("inf")):
            continue                      # stale entry — skip
        for v, w in graph.adj[u]:
            nd = d + w
            if nd < dist.get(v, float("inf")):
                dist[v] = nd              # found a cheaper route to v
                heapq.heappush(pq, (nd, v))
    return dist

wg = Graph()
wg.add_edge("A", "B", 1); wg.add_edge("B", "C", 2)
wg.add_edge("A", "C", 5)
print(dijkstra(wg, "A"))               # {'A':0,'B':1,'C':3}  (A-B-C beats A-C)

7 · Bellman-Ford — handles negatives expert advanced

When would an edge ever have a negative cost? It sounds like a maths curiosity until you meet a real one: currency exchange, where converting dollars → euros → yen → dollars might, through a market glitch, leave you with more money than you started — a profit loop. Or a logistics network where some legs earn a rebate. The instant weights can go negative, Dijkstra is off the table (its "finalized means final" promise shatters), and you reach for Bellman-Ford — slower, simpler, and honest about the cases Dijkstra can't handle.

Where Dijkstra was clever — a heap carefully choosing the best node to expand next — Bellman-Ford is brute force, and proud of it. It doesn't try to be smart about order. It just relaxes every single edge in the graph, then does it again, and again — V−1 times total, where V is the number of nodes. The analogy is letting a shortest-path improvement "ripple" across the graph: after one full pass the best distances have propagated one hop further; after V−1 passes they've had enough rounds to reach the farthest node (any shortest path visits at most V−1 edges), so everything has settled. It's the same relax step from Dijkstra — "take the cheaper route to this node if one appears" — just applied blindly and repeatedly instead of in a smart order.

That plodding structure buys a genuinely useful bonus: free negative-cycle detection. After V−1 passes, a correct answer should be stable — no edge should improve any further. So Bellman-Ford does one extra pass and watches: if some edge can still be relaxed, distances would keep shrinking forever, which can only mean a loop whose total weight is negative (the currency-arbitrage case). It raises an error rather than pretending a "shortest" path exists, because with a negative cycle none does — you could circle it endlessly to get cheaper and cheaper.

The decision rule to carry away is simple and the try-it box below states it plainly: reach for Dijkstra by default because at O((V+E) log V) it's much faster; reach for Bellman-Ford only when negative weights are genuinely possible, accepting its slower O(V·E) in exchange for the one thing Dijkstra cannot do. Choosing Bellman-Ford "just to be safe" on a non-negative graph is the common mistake — you'd pay a real speed penalty for a capability you don't need.

pythondef bellman_ford(edges, nodes, start):   # edges: list of (u, v, w)
    dist = {n: float("inf") for n in nodes}
    dist[start] = 0
    for _ in range(len(nodes) - 1):      # V-1 relaxation passes
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    for u, v, w in edges:                # one more pass -> still improving?
        if dist[u] + w < dist[v]:
            raise ValueError("negative cycle detected")
    return dist

8 · Minimum spanning tree & union-find expert advanced

Imagine you're wiring up a new office — or a city with fibre, or a chip with traces. You have a set of locations and a price to lay cable between each pair. You need every location connected (a signal can reach any of them), but you're paying by the metre, so you want to spend as little total cable as possible. And laying a loop of cable that circles back on itself is pure waste — if A, B, and C are already joined, a fourth cable closing the triangle connects nothing new. That "connect everything for the least total cost, no redundant loops" problem is a minimum spanning tree (MST), and it shows up anywhere you're building a cheapest network: utilities, clustering data points, even approximating harder routing problems.

The word tree is doing precise work here. To connect V locations you need exactly V−1 edges — any fewer and something's stranded, any more and you've made a cycle (waste). A structure that connects everything with no cycles is, by definition, a tree; the "minimum" means the specific tree whose edges add up to the smallest total weight. So an MST spans every node (nothing left out) at minimum cost.

The intuition for finding one is almost suspiciously simple — it's a greedy strategy called Kruskal's algorithm: sort all the possible edges from cheapest to most expensive (that's the sorting from D6), then walk down that list adding each edge unless it would create a cycle. Take the bargains first; skip any edge whose two endpoints are already connected some other way. Repeat until everything's joined. The diagram runs the three-node case: add A–B (cost 1), add A–C (cost 2), then skip B–C (cost 3) because B and C are already linked through A.

Which raises the one hard question: how do you check "are these two nodes already connected?" quickly? Re-running a traversal for every candidate edge would be painfully slow. This is where a small, brilliant structure earns its place — union-find (also called disjoint-set). It keeps nodes grouped into "connected clumps" and answers two questions blazingly fast: find ("which clump is this node in?") and union ("merge these two clumps"). With two optimisations — path compression (flattening the lookup chain as you climb it) and union-by-rank — each operation runs in near-O(1) amortized time. So an edge that would join two nodes already in the same clump is instantly recognized as a cycle and skipped. The mistake worth flagging: union-find only tracks connectivity, not distances or paths — don't reach for it to find a route, only to answer "same group or not?" The lab builds union-find first, then Kruskal on top of it.

pythonclass UnionFind:
    def __init__(self, nodes):
        self.parent = {n: n for n in nodes}   # each node its own set
    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]  # path compression
            x = self.parent[x]
        return x
    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                # already connected -> would make a cycle
        self.parent[ra] = rb
        return True

def kruskal(nodes, edges):            # edges: list of (w, u, v)
    uf = UnionFind(nodes)
    mst, total = [], 0
    for w, u, v in sorted(edges):     # cheapest edges first
        if uf.union(u, v):             # add only if it connects two sets
            mst.append((u, v, w)); total += w
    return mst, total

edges = [(1,"A","B"), (3,"B","C"), (2,"A","C")]
print(kruskal(["A","B","C"], edges))   # ([('A','B',1),('A','C',2)], 3)

Exercises expert

🎯 Interview practice interview

The interview questions this topic gets asked — worked, with code. For the full pattern catalog see D8 · Big Tech DSA patterns.

pythondef num_islands(grid):
    rows, cols = len(grid), len(grid[0])
    def sink(r, c):
        if 0 <= r < rows and 0 <= c < cols and grid[r][c] == "1":
            grid[r][c] = "0"
            sink(r+1,c); sink(r-1,c); sink(r,c+1); sink(r,c-1)
    n = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1":
                n += 1; sink(r, c)
    return n

pythonfrom collections import deque
def can_finish(n, prereqs):
    adj = {i: [] for i in range(n)}; indeg = [0]*n
    for a, b in prereqs:
        adj[b].append(a); indeg[a] += 1
    q = deque(i for i in range(n) if indeg[i]==0); done = 0
    while q:
        node = q.popleft(); done += 1
        for nxt in adj[node]:
            indeg[nxt] -= 1
            if indeg[nxt]==0: q.append(nxt)
    return done == n

Checkpoint expert

from collections import defaultdict

def build(edges):
    g = defaultdict(list)
    for u, v in edges:
        g[u].append(v); g[v].append(u)   # undirected -> both directions
    return g

g = build([(1, 2), (1, 3), (2, 4)])
for node in sorted(g):
    print(node, "->", g[node])
# 1 -> [2, 3] ; 2 -> [1, 4] ; 3 -> [1] ; 4 -> [2]

from collections import deque

def bfs_dist(graph, start, goal):      # O(V+E)
    q = deque([(start, 0)]); seen = {start}
    while q:
        node, d = q.popleft()
        if node == goal:
            return d
        for nxt in graph[node]:
            if nxt not in seen:
                seen.add(nxt); q.append((nxt, d + 1))
    return -1

g = {1: [2, 3], 2: [4], 3: [4], 4: []}
print(bfs_dist(g, 1, 4))               # 2  (1->2->4)

def has_cycle(graph):                  # O(V+E)
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {u: WHITE for u in graph}
    def dfs(u):
        color[u] = GRAY                # on the current recursion stack
        for v in graph[u]:
            if color[v] == GRAY:       # back-edge -> cycle
                return True
            if color[v] == WHITE and dfs(v):
                return True
        color[u] = BLACK               # fully explored
        return False
    return any(color[u] == WHITE and dfs(u) for u in graph)

print(has_cycle({1: [2], 2: [3], 3: [1]}))   # True
print(has_cycle({1: [2], 2: [3], 3: []}))    # False

from collections import deque, defaultdict

def topo_sort(graph):                  # O(V+E)
    indeg = defaultdict(int)
    for u in graph:
        indeg.setdefault(u, 0)
        for v in graph[u]:
            indeg[v] += 1
    q = deque([u for u in indeg if indeg[u] == 0])
    order = []
    while q:
        u = q.popleft(); order.append(u)
        for v in graph[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return order if len(order) == len(indeg) else None  # None = cycle

print(topo_sort({"a": ["b", "c"], "b": ["d"], "c": ["d"], "d": []}))
# ['a', 'b', 'c', 'd']

import heapq

def dijkstra(graph, src):              # graph: node -> list of (neighbor, weight)
    dist = {src: 0}
    pq = [(0, src)]                    # (distance, node)
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist.get(u, float("inf")):
            continue                   # stale entry, skip
        for v, w in graph[u]:
            nd = d + w
            if nd < dist.get(v, float("inf")):
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist

g = {"a": [("b", 1), ("c", 4)], "b": [("c", 2), ("d", 5)],
     "c": [("d", 1)], "d": []}
print(dijkstra(g, "a"))   # {'a':0,'b':1,'c':3,'d':4}

def num_islands(grid):                 # O(R*C)
    if not grid: return 0
    R, C = len(grid), len(grid[0])
    def sink(r, c):
        if 0 <= r < R and 0 <= c < C and grid[r][c] == "1":
            grid[r][c] = "0"           # mark visited in place
            sink(r+1, c); sink(r-1, c); sink(r, c+1); sink(r, c-1)
    count = 0
    for r in range(R):
        for c in range(C):
            if grid[r][c] == "1":
                count += 1; sink(r, c) # flood the whole island
    return count

grid = [list("11000"), list("11000"), list("00100"), list("00011")]
print(num_islands(grid))               # 3

Knowledge check check yourself