Graphs

This builds the adjacency list from the diagram as a real Python class. A Graph object holds a dictionary that maps each node to the list of nodes it points to, plus a flag saying whether edges are one-way (directed) or two-way.

1. self.adj = defaultdict(list) is the storage. A defaultdict(list) is a dictionary that automatically starts a fresh empty list the first time you touch a new key — so you never have to check "does this node exist yet?" before appending.
2. add_edge(u, v, w=1) records an edge from u to v with weight w (a cost; default 1). It appends the pair (v, w) to u's neighbour list — storing the neighbour and the edge's cost together.
3. if not self.directed: — for a two-way graph it also adds the reverse edge v → u, so both nodes list each other. A directed graph skips this, keeping the edge one-way.
4. The demo builds a directed DevOps graph: build → test, test → deploy, build → lint. print(dict(g.adj)) shows the finished map.

What the output means: You see the adjacency dict, e.g. {'build': [('test', 1), ('lint', 1)], 'test': [('deploy', 1)]} — each node listed with its outgoing neighbours and weights.

Try this: Change Graph(directed=True) to Graph(directed=False) and reprint. Now every edge appears in both directions — that is the only difference between a one-way and a two-way graph.

Two functions here. bfs visits every reachable node in ring order; shortest_path reuses the same idea to return the actual shortest route between two nodes. Both rely on a queue — a line where the first item added is the first removed (FIFO), exactly like a checkout line.

1. visited = {start} is a set of nodes we've already seen, so we never process one twice. q = deque([start]) is the queue, primed with the start node.
2. node = q.popleft() takes the node from the front of the queue (FIFO). Because we add nodes in the order we discover them and remove from the front, we naturally drain one ring before the next.
3. For each neighbour nbr, if it's not already visited we mark it visited and append it to the back of the queue. Marking it now (on enqueue) is critical — see the warning box below.
4. shortest_path is the same loop, but the queue holds whole paths (lists of nodes) instead of single nodes. It grows each path with path + [nbr]. The first path whose last node equals goal is returned — and because BFS reaches nodes nearest-first, that first path is the shortest one.

What the output means: bfs returns the visit order as a list, e.g. ['S', 'A', 'B', 'D', 'E']. shortest_path returns the node list of the shortest route, e.g. ['S', 'A', 'D'], or None if the goal can't be reached.

Try this: Trace shortest_path for a start with two routes to the goal — a short one and a long one. BFS returns the short one because it fills nearer rings first, so the goal is found via the fewest edges before the long route ever finishes.

Two ways to write DFS. dfs_recursive lets Python's own function-call stack do the remembering; dfs_iterative keeps an explicit list as the stack. They visit the same nodes — just differently under the hood.

1. dfs_recursive(graph, node, visited=None) marks node visited, then calls itself on each unvisited neighbour. Each nested call dives one level deeper; when a call finds no new neighbours it returns (that's the backtrack), and the caller continues with its next neighbour.
2. if visited is None: visited = set() creates the shared "seen" set on the very first call. (A fresh set each top-level call — never reuse a mutable default.)
3. dfs_iterative replaces recursion with a plain list stack = [start]. node = stack.pop() removes the last item (LIFO), which is why we go deep: the most recently pushed neighbour is explored next.
4. if node in visited: continue — because a node can be pushed more than once here, we skip it if already processed. The iterative form avoids Python's recursion depth limit, so it's the safe choice for very deep or large graphs.

What the output means: Both return the set of all nodes reachable from the start, e.g. {'S', 'A', 'C', 'B'}. The set doesn't record order — use a list if you want the exact visit sequence.

Try this: Give the graph a cycle (e.g. an edge that loops back to the start). The visited set stops both versions from looping forever — remove that check and the recursive one will crash with a stack overflow.

This is Kahn's algorithm for topological sort in code. It counts how many prerequisites each node has, starts with the ones that have none, and "completes" them one at a time — freeing up their dependents as it goes.

1. indeg = {n: 0 for n in nodes} then the double loop counts, for every node, how many edges point into it (its in-degree). indeg[v] += 1 runs once per incoming edge.
2. q = deque([n for n in nodes if indeg[n] == 0]) seeds the queue with every node that has no prerequisites — these are safe to do immediately.
3. The loop pops a ready node u, appends it to order, then for each neighbour v does indeg[v] -= 1 — treating "u is done" as removing u's outgoing edges. When a neighbour's count hits 0, all its prerequisites are done, so it joins the queue.
4. if len(order) != len(nodes): — if we couldn't order every node, some were stuck with a permanent prerequisite, i.e. a cycle. We raise an error instead of returning a broken order.

What the output means: A valid ordering list, e.g. ['build', 'test', 'lint', 'deploy']. Several orders can be valid — any order that never puts a task before its prerequisite is correct.

Try this: Add an edge that creates a loop (e.g. make deploy a prerequisite of build). Now no node ever reaches in-degree 0 after the first pass, len(order) falls short, and the cycle error fires — that is the cycle detector.

This is Dijkstra in code. It keeps a dist map of the best-known distance to each node and a min-heap (heapq) that always pops the closest unfinished node next — that ordering is what makes the answer correct.

1. dist = {start: 0} — the start is 0 away from itself; every other node is unknown (treated as infinity) until we find a route. pq = [(0, start)] is the heap of (distance, node) pairs, ordered by distance.
2. d, u = heapq.heappop(pq) pulls out the smallest-distance pair — the closest node we haven't finalized. Processing nodes closest-first is the heart of Dijkstra.
3. if d > dist.get(u, float("inf")): continue skips stale heap entries: we may have pushed u more than once, and if we already have a better distance for it, this older, larger entry is ignored.
4. For each neighbour, nd = d + w is the cost to reach v through u. If that beats v's current best, we relax: record dist[v] = nd and push (nd, v) so v gets re-examined with its improved distance.

What the output means: A dict of shortest distances from the start, e.g. {'A': 0, 'B': 1, 'C': 3} — confirming the A→B→C detour (3) beats the direct A→C edge (5).

Try this: Add an edge A→C with weight 2. Now the direct route ties/beats the detour and dist['C'] becomes 2 — watch Dijkstra pick whichever total is smallest.

Bellman-Ford also finds shortest paths, but unlike Dijkstra it works even when some edge weights are negative. It's simpler and slower: instead of a clever heap order, it just relaxes every edge, over and over.

1. dist = {n: float("inf") for n in nodes} starts every node at infinity except the start (dist[start] = 0) — nothing is reachable yet.
2. for _ in range(len(nodes) - 1): repeats the relaxation V−1 times (V = number of nodes). That many passes is provably enough for the shortest distance to "flow" all the way across the graph.
3. Inside, if dist[u] + w < dist[v]: dist[v] = dist[u] + w is the same relax step as Dijkstra — take a cheaper route to v if going through u is better.
4. The extra final pass is the clever bit: if any edge can still be relaxed after V−1 passes, distances would shrink forever — a negative cycle — so it raises an error.

What the output means: A dict of shortest distances from the start (like Dijkstra's), or a raised ValueError("negative cycle detected") if a negative loop makes shortest paths meaningless.

Try this: Use Dijkstra when all weights are ≥ 0 (faster). Reach for Bellman-Ford only when negative weights are possible — its one job Dijkstra can't do.

This implements union-find (the connectivity tracker) and then Kruskal's MST on top of it. Union-find answers one question very fast: "are these two nodes already in the same connected group?"

1. self.parent = {n: n for n in nodes} starts with every node in its own group (each node points to itself as its group's representative).
2. find(x) follows parent links up to the group's root (the node that points to itself). The line self.parent[x] = self.parent[self.parent[x]] is path compression — it flattens the chain as it climbs, making future look-ups nearly instant.
3. union(a, b) finds both roots. If they're the same, a and b are already connected, so it returns False (joining them would make a cycle). Otherwise it links one root under the other and returns True.
4. kruskal loops edges via sorted(edges) (cheapest first, since each edge is stored as (w, u, v) — weight leads). It keeps an edge only when uf.union(u, v) returns True, i.e. it connected two separate groups.

What the output means: A pair: the list of chosen MST edges and their total weight, e.g. ([('A','B',1), ('A','C',2)], 3) — the cheapest cycle-free way to connect all nodes. The B–C edge (3) is skipped because it would form a cycle.

Try this: Change A–C from weight 2 to 4. Now B–C (3) is cheaper, so Kruskal picks a different pair of edges — but always the two cheapest that keep the graph cycle-free.

This is the classic interview problem "Number of Islands". You get a grid of "1" (land) and "0" (water); count how many separate islands of connected land there are. A grid is secretly a graph — each cell is a node, and its up/down/left/right neighbours are its edges.

1. rows, cols = len(grid), len(grid[0]) reads the grid's size. We'll scan every cell once, left-to-right, top-to-bottom.
2. sink(r, c) is a DFS "flood fill": if the cell is on the grid and is land ("1"), it turns it to water ("0") so it's never counted again, then recursively sinks its four neighbours — spreading across the whole connected island.
3. The double for loop walks every cell. Each time it hits a "1" that hasn't been sunk yet, that's a new island: it does n += 1 and then sink(r, c) erases the entire island so its other cells won't be re-counted.
4. Because sink flattens each island the moment it's found, every remaining "1" the scan meets must belong to a fresh island — so the count is exact.

What the output means: An integer — the number of separate land islands. For a grid with two disconnected land blobs it returns 2.

Try this: This is just DFS run from each unvisited node, which is also how you count "connected components" in any graph (exercise 1 above). Grids are graphs in disguise.

This is "Course Schedule": given courses and prerequisite pairs, can you finish them all? You can — unless the prerequisites form a cycle (course X needs Y, Y needs X). It's topological sort (Kahn's algorithm) used purely as a cycle detector.

1. Each prereqs pair [a, b] means "must take b before a". adj[b].append(a) records the edge b → a, and indeg[a] += 1 counts that a now has one more prerequisite.
2. q = deque(i ... if indeg[i]==0) starts with every course that has no prerequisites — the ones you can take right away.
3. The loop takes a ready course, counts it done (done += 1), and for each course that depended on it lowers indeg. When a dependent's count hits 0, its prerequisites are all cleared, so it's enqueued.
4. return done == n — if we managed to "finish" all n courses, there was no cycle (True). If some courses were never freed, they're locked in a prerequisite cycle, so it's impossible (False).

What the output means: True if all courses are completable, False if a circular prerequisite makes it impossible.

Try this: Feed it a cycle like [[0,1],[1,0]] (0 needs 1, 1 needs 0). Neither ever reaches in-degree 0, done stalls below n, and it correctly returns False.