Graph Algorithms — Step-by-Step

Discrete Mathematics — Walkthrough Track · real-life examples, full execution traces, good & bad cases

Notes By Pr. El Hadiq Zouhair

1 / 14

How to read this walkthrough

Eight core algorithms, each presented the same way so you really understand what happens inside:

🌍 Real-life example — a concrete situation the algorithm solves.
Idea & Python — what it does and a short implementation.
Execution trace — the value of every variable (queue, stack, dist, in-degree, heap, colours…) at each iteration and each recursion, on a real example.
✓ Good when / ✗ Poor choice — the situations where the algorithm shines and where it gives a wrong or slow answer (with a trace of the failure).

Algorithms covered: BFS · DFS · Topological sort · Bipartite check · Dijkstra · Bellman–Ford · Minimum Spanning Tree (Kruskal & Prim) · Greedy colouring.

1. Breadth-First Search (BFS)

how many introductions away is one person from another in a small group? BFS finds the shortest chain of friendships ("degrees of separation").

Idea. Explore layer by layer from the source using a FIFO queue. The first time a vertex is reached, the number of edges used is its shortest (hop) distance — so it is final immediately.

Python — BFSfrom collections import deque def bfs(G, s): dist, parent = {s: 0}, {s: None} q = deque([s]) while q: u = q.popleft() # take the oldest frontier vertex for v in G[u]: if v not in dist: # first time seen = shortest dist[v] = dist[u] + 1 parent[v] = u q.append(v) return dist, parent

Example graph. Friendships: Ana–Bilal, Ana–Carla, Bilal–Diego, Carla–Diego, Carla–Eva, Diego–Farah. We run bfs(G, "Ana") and watch the queue and dist at every dequeue:

BFS from Ana — the queue holds the current frontier; dist is final the moment a vertex is dequeued.
Step	Dequeue u	Discovered (v:dist)	Queue after	dist
0	— (init)	—	[Ana]	{Ana:0}
1	Ana	Bilal:1, Carla:1	[Bilal, Carla]	{Ana:0, Bilal:1, Carla:1}
2	Bilal	Diego:2	[Carla, Diego]	{Ana:0, Bilal:1, Carla:1, Diego:2}
3	Carla	Eva:2	[Diego, Eva]	{Ana:0, Bilal:1, Carla:1, Diego:2, Eva:2}
4	Diego	Farah:3	[Eva, Farah]	{Ana:0, Bilal:1, Carla:1, Diego:2, Eva:2, Farah:3}
5	Eva	—	[Farah]	{Ana:0, Bilal:1, Carla:1, Diego:2, Eva:2, Farah:3}
6	Farah	—	[]	{Ana:0, Bilal:1, Carla:1, Diego:2, Eva:2, Farah:3}

edges are all equal (one "hop"): shortest social distance, maze with unit steps, fewest-transfers metro route, network broadcast, puzzles solved in fewest moves. Always $O(n+m)$.

edges have different costs. BFS counts hops, not weight, so on a weighted map it can return a path that uses fewer edges but costs more — use Dijkstra instead.

BFS counts hops, not weight: it would pick A→C (1 hop, cost 20) over the cheaper A→B→C (cost 11).
Path	BFS sees	Real cost
A→C direct	1 hop	20 (expensive)
A→B→C	2 hops	5 + 6 = 11 (cheaper)

2 / 14

2. Depth-First Search (DFS)

exploring all rooms of a maze (or all folders in a file tree): go as deep as you can, then back up and try the next branch.

Idea. Dive deep before backtracking. Iteratively this uses an explicit stack (LIFO); recursively it uses the function call stack. Great for reachability, connected components and cycle detection.

Python — iterative (stack) & recursivedef dfs_iter(G, s): seen, stack = set(), [s] while stack: u = stack.pop() # LIFO → go deep if u not in seen: seen.add(u) stack.extend(v for v in G[u] if v not in seen) return seen def dfs_rec(G, u, seen=None): if seen is None: seen = set() seen.add(u) for v in G[u]: if v not in seen: dfs_rec(G, v, seen) # recursion = implicit stack return seen

Iterative trace on the maze a–b, a–c, b–d, c–d, d–e (the explicit stack):

Iterative DFS from a — the explicit stack replaces the call stack; LIFO order makes it dive deep first.
Step	Action	Pushed	Stack after	Visited
0	— (init)	—	[a]	{}
1	pop a	push [b, c]	[b, c]	[a]
2	pop c	push [d]	[b, d]	[a, c]
3	pop d	push [b, e]	[b, b, e]	[a, c, d]
4	pop e	—	[b, b]	[a, c, d, e]
5	pop b	—	[b]	[a, b, c, d, e]
6	pop b	already seen → skip	[]	[a, b, c, d, e]

Recursive trace on the same graph — watch the call stack grow on enter and unwind on finish (a primed step number marks the backtrack):

Recursive DFS from a — note how the call stack grows on 'enter' and unwinds on 'finish' (backtracking).
Step	Event	Call stack	Visited
1	enter a	→ [a]	[a]
2	enter b	→ [a, b]	[a, b]
3	enter d	→ [a, b, d]	[a, b, d]
4	enter c	→ [a, b, d, c]	[a, b, c, d]
4′	finish c	↑ [a, b, d, c]	[a, b, c, d]
5	enter e	→ [a, b, d, e]	[a, b, c, d, e]
5′	finish e	↑ [a, b, d, e]	[a, b, c, d, e]
5′	finish d	↑ [a, b, d]	[a, b, c, d, e]
5′	finish b	↑ [a, b]	[a, b, c, d, e]
5′	finish a	↑ [a]	[a, b, c, d, e]

you must visit/explore everything: connected components, cycle detection, maze generation, topological sort, flood-fill, reachability (garbage collection).

you need a shortest path — DFS finds a path, rarely the shortest. Also, the recursive version can hit Python's recursion limit on very long chains (thousands of vertices); use the iterative stack version there.

3 / 14

3. Topological sort — ordering courses by prerequisites

in what order can you take the Discrete-Mathematics courses so that every course comes after its prerequisites? Each course is a vertex; an arrow X → Y means "X is required before Y". A valid study plan is a topological order of this DAG.

PL=Propositional Logic · LE=Logical Equivalences · PR=Predicate Logic & Quantifiers · RI=Rules of Inference · ST=Sets · OS=Operations on Sets · RF=Relations & Functions · SS=Sequences & Series · PT=Proof Techniques · MI=Mathematical Induction · CO=Counting · BI=Binomial Identities · GR=Graphs

The prerequisite graph:

Python — the prerequisite DAG (X → courses needing X)prereq = { "PL": ["LE"], # Propositional Logic → Logical Equivalences "LE": ["PR"], # Logical Equivalences → Predicate Logic "PR": ["RI", "ST"], # Predicate Logic → Rules of Inference, Sets "RI": ["PT"], # Rules of Inference → Proof Techniques "ST": ["OS", "CO"], # Sets → Operations on Sets, Counting "OS": ["RF"], # Operations on Sets → Relations & Functions "RF": ["SS", "GR"], # Relations & Functions→ Sequences & Series, Graphs "PT": ["MI"], # Proof Techniques → Mathematical Induction "MI": ["GR"], # Math Induction → Graphs "CO": ["BI"], # Counting → Binomial Identities "SS": [], "BI": [], "GR": [], }

Step 0 — initial in-degree (how many prerequisites each course still has):

Initial in-degree = number of prerequisites. Courses with in-degree 0 can be taken first.
Course	In-degree	Prerequisites
PL	0	— (none)
LE	1	PL
PR	1	LE
RI	1	PR
ST	1	PR
OS	1	ST
RF	1	OS
SS	1	RF
PT	1	RI
MI	1	PT
CO	1	ST
BI	1	CO
GR	2	RF, MI

4 / 14

3a. Topological sort — Kahn's algorithm, iteration by iteration

Python — Kahn (BFS-style)from collections import deque def topo_kahn(G): indeg = {u: 0 for u in G} for u in G: for v in G[u]: indeg[v] += 1 q = deque([u for u in indeg if indeg[u] == 0]) # no prerequisites order = [] while q: u = q.popleft() order.append(u) # take this course for v in G[u]: indeg[v] -= 1 # one prerequisite cleared if indeg[v] == 0: q.append(v) # now unlocked return order if len(order) == len(G) else None # None ⇒ cycle

Every iteration: dequeue an unlocked course, decrement its successors' in-degrees, enqueue any that just hit 0.

Kahn's algorithm on the prerequisite DAG — repeatedly take a course with no unmet prerequisites.
Step	Dequeue	Neighbours' in-degree −1	Newly 0 (enqueue)	Queue after	Order so far
0	— (init)	—	—	[PL]	[]
1	PL	LE:0	[LE]	[LE]	[PL]
2	LE	PR:0	[PR]	[PR]	[PL, LE]
3	PR	RI:0, ST:0	[RI, ST]	[RI, ST]	[PL, LE, PR]
4	RI	PT:0	[PT]	[ST, PT]	[PL, LE, PR, RI]
5	ST	OS:0, CO:0	[OS, CO]	[PT, OS, CO]	[PL, LE, PR, RI, ST]
6	PT	MI:0	[MI]	[OS, CO, MI]	[PL, LE, PR, RI, ST, PT]
7	OS	RF:0	[RF]	[CO, MI, RF]	[PL, LE, PR, RI, ST, PT, OS]
8	CO	BI:0	[BI]	[MI, RF, BI]	[PL, LE, PR, RI, ST, PT, OS, CO]
9	MI	GR:1	—	[RF, BI]	[PL, LE, PR, RI, ST, PT, OS, CO, MI]
10	RF	SS:0, GR:0	[SS, GR]	[BI, SS, GR]	[PL, LE, PR, RI, ST, PT, OS, CO, MI, RF]
11	BI	—	—	[SS, GR]	[PL, LE, PR, RI, ST, PT, OS, CO, MI, RF, BI]
12	SS	—	—	[GR]	[PL, LE, PR, RI, ST, PT, OS, CO, MI, RF, BI, SS]
13	GR	—	—	[]	[PL, LE, PR, RI, ST, PT, OS, CO, MI, RF, BI, SS, GR]

Resulting study plan: PL → LE → PR → RI → ST → PT → OS → CO → MI → RF → BI → SS → GR.

5 / 14

3b. Topological sort — DFS version (recursion), step by step

The same ordering can be produced by DFS: a course is prepended to the plan only once all the courses it unlocks are finished. Watch the recursion enter and finish:

Python — DFS post-order topological sortdef topo_dfs(G): seen, order = set(), [] def visit(u): seen.add(u) for v in G[u]: if v not in seen: visit(v) # recurse first order.insert(0, u) # prepend when finished for u in G: if u not in seen: visit(u) return order

DFS-based topological sort (recursion) — a course is prepended to the order only when its whole prerequisite subtree is finished.
Step	Event	Call stack	Order (prepend on finish)
1	enter PL	→ [PL]	[]
2	enter LE	→ [PL, LE]	[]
3	enter PR	→ [PL, LE, PR]	[]
4	enter RI	→ [PL, LE, PR, RI]	[]
5	enter PT	→ [PL, LE, PR, RI, PT]	[]
6	enter MI	→ [PL, LE, PR, RI, PT, MI]	[]
7	enter GR	→ [PL, LE, PR, RI, PT, MI, GR]	[]
7′	finish GR → prepend	↑ [PL, LE, PR, RI, PT, MI, GR]	[GR]
7′	finish MI → prepend	↑ [PL, LE, PR, RI, PT, MI]	[MI, GR]
7′	finish PT → prepend	↑ [PL, LE, PR, RI, PT]	[PT, MI, GR]
7′	finish RI → prepend	↑ [PL, LE, PR, RI]	[RI, PT, MI, GR]
8	enter ST	→ [PL, LE, PR, ST]	[RI, PT, MI, GR]
9	enter OS	→ [PL, LE, PR, ST, OS]	[RI, PT, MI, GR]
10	enter RF	→ [PL, LE, PR, ST, OS, RF]	[RI, PT, MI, GR]
11	enter SS	→ [PL, LE, PR, ST, OS, RF, SS]	[RI, PT, MI, GR]
11′	finish SS → prepend	↑ [PL, LE, PR, ST, OS, RF, SS]	[SS, RI, PT, MI, GR]
11′	finish RF → prepend	↑ [PL, LE, PR, ST, OS, RF]	[RF, SS, RI, PT, MI, GR]
11′	finish OS → prepend	↑ [PL, LE, PR, ST, OS]	[OS, RF, SS, RI, PT, MI, GR]
12	enter CO	→ [PL, LE, PR, ST, CO]	[OS, RF, SS, RI, PT, MI, GR]
13	enter BI	→ [PL, LE, PR, ST, CO, BI]	[OS, RF, SS, RI, PT, MI, GR]
13′	finish BI → prepend	↑ [PL, LE, PR, ST, CO, BI]	[BI, OS, RF, SS, RI, PT, MI, GR]
13′	finish CO → prepend	↑ [PL, LE, PR, ST, CO]	[CO, BI, OS, RF, SS, RI, PT, MI, GR]
13′	finish ST → prepend	↑ [PL, LE, PR, ST]	[ST, CO, BI, OS, RF, SS, RI, PT, MI, GR]
13′	finish PR → prepend	↑ [PL, LE, PR]	[PR, ST, CO, BI, OS, RF, SS, RI, PT, MI, GR]
13′	finish LE → prepend	↑ [PL, LE]	[LE, PR, ST, CO, BI, OS, RF, SS, RI, PT, MI, GR]
13′	finish PL → prepend	↑ [PL]	[PL, LE, PR, ST, CO, BI, OS, RF, SS, RI, PT, MI, GR]

any "must happen before" structure: course plans, build systems (Make/Gradle), task scheduling, package install order, spreadsheet recalculation. Runs in $O(n+m)$.

the graph has a cycle — then no valid order exists. If two courses were each other's prerequisite (A → B → C → A), Kahn's queue empties before all courses are placed:

Cyclic prerequisites A→B→C→A: the queue empties early, order is incomplete ⇒ Kahn reports 'no valid order'.
Step	Dequeue	note	Queue	Order
0	init	—	[D]	[]
1	D	—	[]	[D]
END	len(order)=1 ≠ 4	queue empty but B,C unprocessed	[]	[D]

6 / 14

4. Bipartite check (two-colouring)

can six lab sessions that conflict be split between exactly two rooms with no two conflicting sessions in the same room? That is asking whether the conflict graph is bipartite.

Idea. BFS-colour the graph alternately 0/1. If an edge ever joins two same-coloured vertices, an odd cycle exists and no 2-split is possible.

Python — 2-colouringfrom collections import deque def two_color(G): color = {} for s in G: if s in color: continue color[s] = 0 q = deque([s]) while q: u = q.popleft() for v in G[u]: if v not in color: color[v] = 1 - color[u] # opposite side q.append(v) elif color[v] == color[u]: return None # clash ⇒ not bipartite return color

Good case — conflict graph 1–4,1–5,2–4,2–6,3–5,3–6 (an even structure). The colour map fills without clash:

Step	Action	Assigned (v=color)	Queue	color map
0	seed 1=0	—	[1]	{1:0}
1	pop 1	4=1, 5=1	[4, 5]	{1:0, 4:1, 5:1}
2	pop 4	2=0	[5, 2]	{1:0, 4:1, 5:1, 2:0}
3	pop 5	3=0	[2, 3]	{1:0, 4:1, 5:1, 2:0, 3:0}
4	pop 2	6=1	[3, 6]	{1:0, 4:1, 5:1, 2:0, 3:0, 6:1}
5	pop 3	—	[6]	{1:0, 4:1, 5:1, 2:0, 3:0, 6:1}
6	pop 6	—	[]	{1:0, 4:1, 5:1, 2:0, 3:0, 6:1}

two-sided structures: assigning to two rooms/shifts/teams, matching applicants to jobs, user–item recommendation graphs, detecting odd cycles.

an odd cycle exists. A triangle u–v–w needs 3 colours; the BFS hits a same-colour edge and returns None:

Step	Action	Assigned (v=color)	Queue	color map
0	seed u=0	—	[u]	{u:0}
1	pop u	v=1, w=1	[v, w]	{u:0, v:1, w:1}
2	pop v	—	[w]	{u:0, v:1, w:1} ⟵ CONFLICT w==v=1

7 / 14

5. Dijkstra — cheapest weighted path

a GPS finds the fastest route across a city where each road has a travel time. Dijkstra settles the nearest place first and expands outward.

Python — Dijkstra with a min-heapimport heapq def dijkstra(G, s): dist = {s: 0} pq = [(0, s)] while pq: d, u = heapq.heappop(pq) # closest unsettled vertex if d > dist.get(u, float("inf")): continue # stale heap entry for v, w in G[u].items(): nd = d + w if nd < dist.get(v, float("inf")): dist[v] = nd heapq.heappush(pq, (nd, v)) return dist

Trace from S on a 6-junction city (weights = minutes). Each pop settles a vertex; relaxations update dist and push onto the heap:

Dijkstra from S — a vertex is settled (final) the first time it is popped; the heap always yields the closest unsettled vertex.
Step	Pop (dist,vertex)	Relaxations (v:old→new)	dist	heap after
0	— (init)	—	{S:0}	[(0, 'S')]
1	pop (0,S) ✓settled	A:∞→7, B:∞→2	{S:0, A:7, B:2}	[(2, 'B'), (7, 'A')]
2	pop (2,B) ✓settled	A:7→5, C:∞→10, D:∞→7	{S:0, A:5, B:2, C:10, D:7}	[(5, 'A'), (7, 'A'), (7, 'D'), (10, 'C')]
3	pop (5,A) ✓settled	C:10→9	{S:0, A:5, B:2, C:9, D:7}	[(7, 'A'), (7, 'D'), (9, 'C'), (10, 'C')]
4	pop (7,A)	stale → skip	{S:0, A:5, B:2, C:9, D:7}	[(7, 'D'), (9, 'C'), (10, 'C')]
5	pop (7,D) ✓settled	E:∞→10	{S:0, A:5, B:2, C:9, D:7, E:10}	[(9, 'C'), (10, 'C'), (10, 'E')]
6	pop (9,C) ✓settled	—	{S:0, A:5, B:2, C:9, D:7, E:10}	[(10, 'C'), (10, 'E')]
7	pop (10,C)	stale → skip	{S:0, A:5, B:2, C:9, D:7, E:10}	[(10, 'E')]
8	pop (10,E) ✓settled	—	{S:0, A:5, B:2, C:9, D:7, E:10}	[]

non-negative weights: road/time/distance maps, network latency routing, cheapest itineraries. $O((n+m)\log n)$ with a heap.

any edge has a negative weight — the "closest first, settle once" rule breaks, because a later negative edge could still lower an already-settled vertex. Use Bellman–Ford instead.

With a negative edge A→B = −4, the true cost to B is −2, but Dijkstra may settle vertices before a negative edge improves them. Greedy 'closest first' is no longer valid.
Step	Action	What happens	dist
1	pop (0,S)	relax A:0→2, B:0→5	{S:0, A:2, B:5}
2	pop (2,A) ✓settled	A has edge A→B = -4 → B:5→-2	{S:0, A:2, B:-2}
—	but B was about to be settled at 5…	Dijkstra already trusts A=2 as final	wrong if a later negative edge could lower it

8 / 14

6. Bellman–Ford — negative weights & cycle detection

currencies and trades where some "edges" are gains (negative cost). Bellman–Ford handles negatives and flags impossible "free-money" loops (negative cycles).

Idea. Relax every edge, repeated $|V|-1$ times. After that many passes all shortest distances are final; one more improving pass would reveal a negative cycle.

Python — Bellman–Forddef bellman_ford(G, s): dist = {v: float("inf") for v in G}; dist[s] = 0 edges = [(u, v, w) for u in G for v, w in G[u].items()] for _ in range(len(G) - 1): # |V|-1 passes for u, v, w in edges: if dist[u] + w < dist[v]: dist[v] = dist[u] + w for u, v, w in edges: # extra pass = cycle test if dist[u] + w < dist[v]: raise ValueError("Negative cycle!") return dist

Trace from S with a negative edge A→C = −4 (no negative cycle). Watch dist stabilise pass by pass:

Bellman–Ford from S — every edge is relaxed once per pass; after |V|−1 = 4 passes all distances are final, even with the negative edge A→C = −4.
Round	Relaxations this pass (v:old→new)	dist after pass
0 (init)	—	{S:0, A:∞, B:∞, C:∞, D:∞}
pass 1	A:∞→6, B:∞→7, C:∞→2, D:∞→11, D:11→4, B:7→4	{S:0, A:6, B:4, C:2, D:4}
pass 2	D:4→1	{S:0, A:6, B:4, C:2, D:1}
pass 3	(no change → stop early possible)	{S:0, A:6, B:4, C:2, D:1}
pass 4	(no change → stop early possible)	{S:0, A:6, B:4, C:2, D:1}

graphs with negative edges, or when you must detect a negative cycle (arbitrage, inconsistent constraints). Simple to implement.

large non-negative graphs: at $O(n\cdot m)$ it is much slower than Dijkstra's $O((n+m)\log n)$. If all weights are $\ge 0$, prefer Dijkstra.

9 / 14

7. Minimum Spanning Tree — Kruskal

a telecom lays fibre to connect five towns at the least total cost. The cheapest connecting network with no redundant loop is a minimum spanning tree.

Idea (Kruskal). Sort edges cheapest-first; add an edge only if its endpoints are in different components (Union-Find), which avoids creating a cycle.

Python — Kruskal + Union-Finddef kruskal(G): parent = {v: v for v in G} def find(x): while parent[x] != x: parent[x] = parent[parent[x]]; x = parent[x] return x def union(x, y): rx, ry = find(x), find(y) if rx == ry: return False # same component → would loop parent[rx] = ry; return True mst = [] for w, u, v in sorted((w,u,v) for u in G for v,w in G[u].items() if u

Trace on towns T1–T5. Edges sorted by weight; each is added or skipped based on the components:

Kruskal on the town network — edges sorted cheapest-first; add an edge only when it joins two different components.
Step	Edge (w) u–v	roots find(u)/find(v)	Action	Components (Union-Find)	MST edges
1	(1) T2–T3	T3 / T3	ADD ✓	{T1}, {T2,T3}, {T4}, {T5}	T2T3
2	(2) T2–T4	T4 / T4	ADD ✓	{T1}, {T2,T3,T4}, {T5}	T2T3, T2T4
3	(3) T1–T3	T4 / T4	ADD ✓	{T1,T2,T3,T4}, {T5}	T2T3, T2T4, T1T3
4	(4) T1–T2	T4 / T4	skip (cycle)	{T1,T2,T3,T4}, {T5}	T2T3, T2T4, T1T3
5	(4) T3–T4	T4 / T4	skip (cycle)	{T1,T2,T3,T4}, {T5}	T2T3, T2T4, T1T3
6	(5) T3–T5	T5 / T5	ADD ✓	{T1,T2,T3,T4,T5}	T2T3, T2T4, T1T3, T3T5
7	(7) T4–T5	T5 / T5	skip (cycle)	{T1,T2,T3,T4,T5}	T2T3, T2T4, T1T3, T3T5

10 / 14

7b. Minimum Spanning Tree — Prim

Idea (Prim). Grow a single tree from a seed town, each step pulling the cheapest edge from the heap that reaches a town not yet in the tree.

Python — Prim with a heapimport heapq def prim(G, start): in_tree = {start}; mst = [] heap = [(w, start, v) for v, w in G[start].items()] heapq.heapify(heap) while heap and len(in_tree) < len(G): w, u, v = heapq.heappop(heap) if v in in_tree: continue # already connected in_tree.add(v); mst.append((u, v, w)) for x, wx in G[v].items(): if x not in in_tree: heapq.heappush(heap, (wx, v, x)) return mst

Trace from T1 — the heap holds candidate edges; skipped pops are edges to towns already connected:

Prim from T1 — grows one tree outward, always taking the cheapest edge to a new town. Same total weight as Kruskal, different build order.
Step	Pop (w) u→v	Action	In tree	MST edges	Heap after
0	seed T1	—	[T1]	—	[(3, 'T1', 'T3'), (4, 'T1', 'T2')]
1	pop (3) T1→T3	ADD ✓	[T1, T3]	T1T3	[(1, 'T3', 'T2'), (4, 'T1', 'T2'), (4, 'T3', 'T4'), (5, 'T3', 'T5')]
2	pop (1) T3→T2	ADD ✓	[T1, T2, T3]	T1T3, T3T2	[(2, 'T2', 'T4'), (4, 'T1', 'T2'), (4, 'T3', 'T4'), (5, 'T3', 'T5')]
3	pop (2) T2→T4	ADD ✓	[T1, T2, T3, T4]	T1T3, T3T2, T2T4	[(4, 'T1', 'T2'), (4, 'T3', 'T4'), (5, 'T3', 'T5'), (7, 'T4', 'T5')]
4	pop (4) T1→T2	v already in tree → skip	[T1, T2, T3, T4]	T1T3, T3T2, T2T4	[(4, 'T3', 'T4'), (5, 'T3', 'T5'), (7, 'T4', 'T5')]
5	pop (4) T3→T4	v already in tree → skip	[T1, T2, T3, T4]	T1T3, T3T2, T2T4	[(5, 'T3', 'T5'), (7, 'T4', 'T5')]
6	pop (5) T3→T5	ADD ✓	[T1, T2, T3, T4, T5]	T1T3, T3T2, T2T4, T3T5	[(7, 'T4', 'T5')]

designing least-cost connected networks: cabling, pipes, power grids, clustering, approximate TSP. Both run in near $O(m\log n)$.

you want the shortest path between two specific nodes — an MST does not give shortest paths (a common mistake); use Dijkstra. MST also needs an undirected, connected, weighted graph.

11 / 14

8. Greedy colouring — and where greed hurts

schedule exams so that no student has two exams at once: vertices = exams, edges = shared students, colours = time slots. A proper colouring is a clash-free timetable.

Idea. Visit vertices in some order; give each the smallest colour not used by its already-coloured neighbours.

Python — greedy colouringdef greedy_coloring(G, order): color = {} for v in order: used = {color[u] for u in G[v] if u in color} c = 0 while c in used: c += 1 # smallest free colour color[v] = c return color

The result depends on the order. Take the "crown" conflict graph — it is 2-colourable (two slots suffice). A bad alternating order forces a third slot:

BAD vertex order on the crown graph (which is 2-colorable): greedy is forced into a 3rd colour.
Step	Vertex	Neighbour colours used	Chosen	coloring
1	a1	[]	0	{a1:0}
2	b1	[]	0	{a1:0, b1:0}
3	a2	[0]	1	{a1:0, b1:0, a2:1}
4	b2	[0]	1	{a1:0, b1:0, a2:1, b2:1}
5	a3	[0, 1]	2	{a1:0, b1:0, a2:1, b2:1, a3:2}
6	b3	[0, 1]	2	{a1:0, b1:0, a2:1, b2:1, a3:2, b3:2}

A better order (one whole side first) recovers the optimal two slots:

GOOD order (all of one side first): greedy uses the optimal 2 colours.
Step	Vertex	Neighbour colours used	Chosen	coloring
1	a1	[]	0	{a1:0}
2	a2	[]	0	{a1:0, a2:0}
3	a3	[]	0	{a1:0, a2:0, a3:0}
4	b1	[0]	1	{a1:0, a2:0, a3:0, b1:1}
5	b2	[0]	1	{a1:0, a2:0, a3:0, b1:1, b2:1}
6	b3	[0]	1	{a1:0, a2:0, a3:0, b1:1, b2:1, b3:1}

fast, simple conflict-avoidance with few colours when a good order (e.g. largest-degree-first) is used: timetables, register allocation, frequency assignment.

you need the minimum number of colours guaranteed. Greedy is not optimal — a poor order can use far more colours than necessary (3 instead of 2 above; arbitrarily many on larger crown graphs). Exact colouring is NP-hard.

12 / 14

Summary — what each trace taught us

Algorithm	State you track	Best for	Avoid when
BFS	queue, dist	fewest-hops path	weighted costs
DFS	stack / call stack, visited	explore, components, cycles	shortest path; very deep recursion
Topological sort	in-degree, queue / recursion	prerequisite ordering	graph has a cycle
Bipartite check	colour map, queue	two-group split / matching	odd cycles present
Dijkstra	dist, heap, settled set	cheapest path, weights ≥ 0	negative weights
Bellman–Ford	dist per pass	negative weights, cycle detection	large non-negative graphs (slow)
MST (Kruskal/Prim)	Union-Find / heap, tree edges	cheapest connecting network	shortest pairwise path
Greedy colouring	neighbour colours, colour map	fast conflict-free assignment	need provably minimum colours

Notes By Pr. El Hadiq Zouhair

13 / 14

End

Now trace them yourself

Re-run each example by hand and check your variable states against these tables.

Notes By Pr. El Hadiq Zouhair

14 / 14