Graphs Basics Checkpoint
A review of this module. Skip it if you feel confident; the next module does not need it.
Fix the mistakes
The slips that cost marks in this module. Spot each one, then check the fix.
This checkpoint mixes everything from the module: components, shortest steps on a grid, cycles and task order. Decide which method the problem needs, then write it.
Pick the tool from the clue
Fewest edges or fewest moves points to BFS. "Is there a path", "how many groups" and "is there a cycle" point to DFS or BFS with a seen set. Tasks that must come in order point to a topological sort on a directed graph.
Example 1 · Friend groups
def build(n, edges, directed=False): graph = [[] for _ in range(n)] for a, b in edges: graph[a].append(b) if not directed: graph[b].append(a) return graph
def components(n, graph): seen, count = set(), 0 for start in range(n): if start in seen: continue count += 1 seen.add(start) stack = [start] while stack: for nxt in graph[stack.pop()]: if nxt not in seen: seen.add(nxt) stack.append(nxt) return count
people = ["Asha", "Ben", "Chen", "Dia", "Eli"]index = {name: i for i, name in enumerate(people)}friends = [("Asha", "Ben"), ("Chen", "Dia")]edges = [(index[a], index[b]) for a, b in friends]print(components(len(people), build(len(people), edges)))3
What this code does
- Names become numbers with
enumerate, so the usual graph code works. - The groups are Asha and Ben, Chen and Dia, and Eli alone.
Grids with walls: BFS over cells
A maze is a grid graph. BFS from the start gives the fewest steps, and cells hold the walls instead of an adjacency list.
def steps(grid, start, goal): rows, cols = len(grid), len(grid[0]) dist = {start: 0} queue = deque([start]) while queue: r, c = queue.popleft() if (r, c) == goal: return dist[(r, c)] for dr, dc in DIRS: nr, nc = r + dr, c + dc if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] != "#" and (nr, nc) not in dist: dist[(nr, nc)] = dist[(r, c)] + 1 queue.append((nr, nc)) return -1Example 2 · Steps through a maze
from collections import deque
DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]
def steps(grid, start, goal): rows, cols = len(grid), len(grid[0]) dist = {start: 0} queue = deque([start]) while queue: r, c = queue.popleft() if (r, c) == goal: return dist[(r, c)] for dr, dc in DIRS: nr, nc = r + dr, c + dc if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] != "#" and (nr, nc) not in dist: dist[(nr, nc)] = dist[(r, c)] + 1 queue.append((nr, nc)) return -1
grid = ["S.#.", "..#.", "...E"]print(steps(grid, (0, 0), (2, 3)))blocked = ["S#E"]print(steps(blocked, (0, 0), (0, 2)))5 -1
What this code does
- The wall column forces the route round the bottom, so the fewest steps is 5.
- In the second grid the wall cuts the row in two, so the answer is -1.
The dictionary is the seen set and the distance table. Return -1 when the queue empties without reaching the goal.
Check before you submit
Mark nodes when you add them to the queue. Loop over range(n) so isolated nodes count. Check grid bounds before indexing. Ask whether edges are directed, and whether the input can repeat an edge or hold a self-loop.
Example 3 · Can every course be taken?
def build(n, edges, directed=False): graph = [[] for _ in range(n)] for a, b in edges: graph[a].append(b) if not directed: graph[b].append(a) return graph
from collections import deque
def topo_order(n, graph): indeg = [0] * n for node in range(n): for nxt in graph[node]: indeg[nxt] += 1 queue = deque(v for v in range(n) if indeg[v] == 0) order = [] while queue: node = queue.popleft() order.append(node) for nxt in graph[node]: indeg[nxt] -= 1 if indeg[nxt] == 0: queue.append(nxt) return order
ok = build(4, [(0, 1), (1, 2), (0, 3)], directed=True)bad = build(4, [(0, 1), (1, 2), (2, 0)], directed=True)print(len(topo_order(4, ok)) == 4)print(len(topo_order(4, bad)) == 4)True False
What this code does
- Without a cycle every node can be removed, so the first answer is True.
- The loop 0, 1, 2 keeps its nodes waiting for each other, so the second answer is False.
Module quiz
Questions from the whole module. Your first answer is your score.
Problems
Graded easy to hard, using everything from this module.
Try each one yourself first. Use the hint if you get stuck. Mark it as done when it works.
Exercise 1· Easy
Nodes 0 to 4 have undirected edges [(0, 1), (1, 2), (3, 4)]. Print the number of components.
2
Exercise 2· Easy
Print the fewest edges from 0 to 4 in the undirected edges [(0, 1), (1, 2), (2, 4), (0, 3), (3, 4)].
2
Exercise 3· Easy
Print True or False: can node 0 reach node 3 in the directed edges [(0, 1), (1, 2), (3, 2)]?
False
Exercise 4· Medium
Print the number of islands in ["1010", "0101", "1010"].
6
Exercise 5· Medium
Print the fewest steps from S (top-left) to E (bottom-right) in the maze ["S.#", ".#.", "..E"], where # is a wall.
4
Exercise 6· Medium
Print True or False: does the undirected graph with 6 nodes and edges [(0, 1), (1, 2), (2, 0), (3, 4)] have a cycle?
True
Exercise 7· Hard
Tasks 0 to 5 have the directed edges [(5, 2), (5, 0), (4, 0), (4, 1), (2, 3), (3, 1)]. Print one valid order as a list.
[4, 5, 2, 0, 3, 1]
Exercise 8· Hard
Print the fewest steps in the maze ["S..#", ".#..", "...E"] that avoids #, then print -1 on the next line for the maze ["S#E"].
5 -1
Interview questions
Questions interviewers ask on this topic.
Finish up
Mark complete & continue
Next: Must-do problems: Graphs Basics and Traversal