Graph Algorithms Checkpoint

Optional

30 min · Intermediate

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 all five tools on plans, networks and routes. First decide which algorithm the clue points to, then write it.

Choose the algorithm from the clue

Read the problem for its key words. Rules like "A before B" mean a topological sort. Groups that merge or "are they connected" mean Union-Find. "Cheapest route" means Dijkstra when no cost is negative.

Order with rules, or a cycle check on a directed graph: Kahn or DFS.
Connected groups, or a loop in an undirected graph: Union-Find.
Cheapest route from one start: BFS, Dijkstra or Bellman-Ford by weight type.
Connect everything at the least cost: Kruskal or Prim.

Kahn with levels

Kahn's algorithm can also count rounds. A task that becomes ready after its slowest prerequisite sits one level higher. The largest level is the minimum number of rounds, if tasks in a round run in parallel.

Python

1level = [1] * n2queue = deque(i for i in range(n) if indeg[i] == 0)3while queue:4    u = queue.popleft()5    for v in graph[u]:6        level[v] = max(level[v], level[u] + 1)7        indeg[v] -= 18        if indeg[v] == 0:9            queue.append(v)

Example 1 · Minimum rounds for a plan

Python

1from collections import deque2
3n = 64rules = [(0, 2), (1, 2), (2, 3), (2, 4), (4, 5)]5graph = [[] for _ in range(n)]6indeg = [0] * n7for u, v in rules:8    graph[u].append(v)9    indeg[v] += 110level = [1] * n11queue = deque(i for i in range(n) if indeg[i] == 0)12while queue:13    u = queue.popleft()14    for v in graph[u]:15        level[v] = max(level[v], level[u] + 1)16        indeg[v] -= 117        if indeg[v] == 0:18            queue.append(v)19
20print(max(level))

Output

What this code does

Tasks 0 and 1 run in round 1, task 2 in round 2, tasks 3 and 4 in round 3, and task 5 in round 4.
If Kahn stopped early, the rules would contain a cycle and no plan would exist.

This is still O(V + E). The answer is max(level).

Union-Find in weight order

Process roads from the cheapest. The moment two places become connected, the last road added is the cheapest "largest road" on any route between them. That is the bottleneck, and it needs only a sort and Union-Find.

Python

1for u, v, w in sorted(edges, key=lambda e: e[2]):2    ru, rv = find(parent, u), find(parent, v)3    if ru != rv:4        parent[ru] = rv5    if find(parent, 0) == find(parent, n - 1):6        print(w)7        break

Example 2 · Smallest road limit that connects two towns

Python

1def find(parent, x):2    while parent[x] != x:3        parent[x] = parent[parent[x]]4        x = parent[x]5    return x6
7
8n = 59edges = [(0, 1, 7), (1, 2, 3), (0, 2, 9), (2, 3, 5), (3, 4, 4), (1, 4, 12)]10parent = list(range(n))11for u, v, w in sorted(edges, key=lambda e: e[2]):12    ru, rv = find(parent, u), find(parent, v)13    if ru != rv:14        parent[ru] = rv15    if find(parent, 0) == find(parent, n - 1):16        print(w)17        break

Output

What this code does

After roads 3, 4, 5 and 7 are added, towns 0 and 4 are connected. The largest road on that route is 7.
The route 0 → 2 → 3 → 4 uses a road of 9, so its largest road is bigger than 7.

Example 3 · Time for a signal to reach every node

Python

1import heapq2
3
4def dijkstra(graph, start):5    dist = [float('inf')] * len(graph)6    dist[start] = 07    heap = [(0, start)]8    while heap:9        d, u = heapq.heappop(heap)10        if d > dist[u]:11            continue12        for v, w in graph[u]:13            if d + w < dist[v]:14                dist[v] = d + w15                heapq.heappush(heap, (d + w, v))16    return dist17
18
19graph = [[(1, 2), (2, 4)], [(2, 1), (3, 7)], [(3, 3)], []]20dist = dijkstra(graph, 0)21print(max(dist) if max(dist) != float('inf') else -1)

Output

What this code does

A signal travels along directed edges. The last node to receive it decides the total time.
If any distance is infinity, some node is never reached and the answer is -1.

Sorting costs O(E log E). The loop adds almost O(E).

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

Print a topological order from Kahn's algorithm for 4 nodes and edges (0,1), (0,2), (1,3), (2,3).

Expected output

[0, 1, 2, 3]

Exercise 2· Easy

Print the number of connected components of 8 nodes with edges (0,1), (2,3), (3,4), (5,6) using Union-Find.

Expected output

Exercise 3· Easy

Print the shortest distance from node 0 to node 4 for the undirected edges (0,1,2), (1,4,9), (0,2,3), (2,3,1), (3,4,2).

Expected output

Exercise 4· Medium

Print True if the directed graph with edges (0,1), (1,2), (2,3), (3,1) has a cycle, otherwise False.

Expected output

True

Exercise 5· Medium

Print the total weight of the minimum spanning tree for 5 nodes and edges (0,1,2), (0,2,3), (1,2,1), (1,3,4), (2,3,5), (3,4,2), (2,4,7).

Expected output

Exercise 6· Medium

Print the Bellman-Ford distance from node 0 to node 3 for directed edges (0,1,5), (0,2,2), (2,1,-4), (1,3,3).

Expected output

Exercise 7· Hard

Print the minimum number of rounds to finish 7 tasks with rules (0,3), (1,3), (3,4), (2,4), (4,5), (4,6) if tasks in a round run in parallel.

Expected output

Exercise 8· Hard

Print the smallest possible largest road on any route from town 0 to town 5, for roads (0,1,4), (1,2,6), (2,5,3), (0,3,8), (3,5,5), (1,4,2), (4,5,9).

Expected output

Interview questions

Questions interviewers ask on this topic.

Finish up

Mark complete & continue

Next: Must-do problems: Graph Algorithms

1level = [1] * n2queue = deque(i for i in range(n) if indeg[i] == 0)3while queue:4 u = queue.popleft()5 for v in graph[u]:6 level[v] = max(level[v], level[u] + 1)7 indeg[v] -= 18 if indeg[v] == 0:9 queue.append(v)

1from collections import deque2 3n = 64rules = [(0, 2), (1, 2), (2, 3), (2, 4), (4, 5)]5graph = [[] for _ in range(n)]6indeg = [0] * n7for u, v in rules:8 graph[u].append(v)9 indeg[v] += 110level = [1] * n11queue = deque(i for i in range(n) if indeg[i] == 0)12while queue:13 u = queue.popleft()14 for v in graph[u]:15 level[v] = max(level[v], level[u] + 1)16 indeg[v] -= 117 if indeg[v] == 0:18 queue.append(v)19 20print(max(level))

1for u, v, w in sorted(edges, key=lambda e: e[2]):2 ru, rv = find(parent, u), find(parent, v)3 if ru != rv:4 parent[ru] = rv5 if find(parent, 0) == find(parent, n - 1):6 print(w)7 break

1def find(parent, x):2 while parent[x] != x:3 parent[x] = parent[parent[x]]4 x = parent[x]5 return x6 7 8n = 59edges = [(0, 1, 7), (1, 2, 3), (0, 2, 9), (2, 3, 5), (3, 4, 4), (1, 4, 12)]10parent = list(range(n))11for u, v, w in sorted(edges, key=lambda e: e[2]):12 ru, rv = find(parent, u), find(parent, v)13 if ru != rv:14 parent[ru] = rv15 if find(parent, 0) == find(parent, n - 1):16 print(w)17 break

1import heapq2 3 4def dijkstra(graph, start):5 dist = [float('inf')] * len(graph)6 dist[start] = 07 heap = [(0, start)]8 while heap:9 d, u = heapq.heappop(heap)10 if d > dist[u]:11 continue12 for v, w in graph[u]:13 if d + w < dist[v]:14 dist[v] = d + w15 heapq.heappush(heap, (d + w, v))16 return dist17 18 19graph = [[(1, 2), (2, 4)], [(2, 1), (3, 7)], [(3, 3)], []]20dist = dijkstra(graph, 0)21print(max(dist) if max(dist) != float('inf') else -1)

1from collections import deque2 3graph = [[2], [2], [3], []]4indeg = [0, 0, 2, 1]5queue = deque([0, 1])6order = []7while queue:8 u = queue.popleft()9 order.append(u)10 for v in graph[u]:11 indeg[v] -= 112 if indeg[v] == 0:13 queue.append(v)14print(order)

1parent = list(range(5))2 3 4def find(x):5 while parent[x] != x:6 x = parent[x]7 return x8 9 10count = 511for a, b in [(0, 1), (1, 2), (2, 0), (3, 4)]:12 ra, rb = find(a), find(b)13 if ra != rb:14 parent[ra] = rb15 count -= 116print(count)

Choose the algorithm from the clue

Kahn with levels

What this code does

Union-Find in weight order

What this code does

What this code does

Exercise 1· Easy

Exercise 2· Easy

Exercise 3· Easy

Exercise 4· Medium

Exercise 5· Medium

Exercise 6· Medium

Exercise 7· Hard

Exercise 8· Hard

Choose the algorithm from the clue

Kahn with levels

What this code does

Union-Find in weight order

What this code does

What this code does

Tasks have "must finish before" rules. You need a valid order. Which algorithm fits?

Edges arrive one by one and you must answer "are these two nodes connected?" after each. Which fits?

Roads cost 0 or more and you need the cheapest route from one depot. Which fits?

Some edges are negative and you need distances from one start. Which fits?

You need the distance between every pair of 200 towns. Which is the simplest to write?

You must connect all offices with cables at the least total cost. Which fits?

What does this print?

What does this print?

Kahn's algorithm returns fewer nodes than the graph has. What do you conclude?

Kruskal keeps 3 edges on a graph with 6 nodes. What does that mean?

Which pair has the right costs?

Why is the heap tuple (distance, node) and not (node, distance)?

Exercise 1· Easy

Exercise 2· Easy

Exercise 3· Easy

Exercise 4· Medium

Exercise 5· Medium

Exercise 6· Medium

Exercise 7· Hard

Exercise 8· Hard

Q1How do you decide which graph algorithm to use?

Q2How do you detect a cycle in a directed graph and in an undirected graph?

Q3How are Dijkstra and Prim alike and different?

Q4State the time costs of the five algorithms from this module.

Q5Which of them need recursion, and how do you avoid the Python limit?

Tasks have "must finish before" rules. You need a valid order. Which algorithm fits?

Edges arrive one by one and you must answer "are these two nodes connected?" after each. Which fits?

Roads cost 0 or more and you need the cheapest route from one depot. Which fits?

Some edges are negative and you need distances from one start. Which fits?

You need the distance between every pair of 200 towns. Which is the simplest to write?

You must connect all offices with cables at the least total cost. Which fits?

What does this print?

What does this print?

Kahn's algorithm returns fewer nodes than the graph has. What do you conclude?

Kruskal keeps 3 edges on a graph with 6 nodes. What does that mean?

Which pair has the right costs?

Why is the heap tuple (distance, node) and not (node, distance)?

Q1How do you decide which graph algorithm to use?

Q2How do you detect a cycle in a directed graph and in an undirected graph?

Q3How are Dijkstra and Prim alike and different?

Q4State the time costs of the five algorithms from this module.

Q5Which of them need recursion, and how do you avoid the Python limit?