BMI2224 Algorithms

Week 11: Minimum Spanning

Tree(MST) Problem
Asst. Prof. Dr. Arzum Karataş

2025-Spring
In the last Lecture…
Some complex systems are here:
◦ Social networks
◦ Biological networks (chemical bond, protein-protein interaction etc.)
◦ Transportation networks (the interstate highway system etc.)
◦ The Internet

• We learn that graphs represent and organize complex systems of

interconnected components.
◦ We learn graph terminology including the definition of "Neighbor,
Path,Path Length, Cycle, Reachability of a node, Connected Graph,
Complete Graph".
2
We talked about the type of graphs.

Directed, Undirected, Undirected, Directed,

unweighted graph unweighted graph unweighted graph weighted graph

Graphs: No restrictions.Graphs can have cycles, no parent/child relationship,

no root node.

We store and represent graphs in implementation as the following ways:

1- Adjacency List (either maps or linked lists)
2- Adjacency Matrix (2D arrays)

3
Searching for a path from one node(vertex) to another:
◦ Sometimes, we just want any path (or want to know there is a
path).
◦ Sometimes, we want to minimize path length (# of edges).
◦ Sometimes, we want to minimize path cost (sum of edge
weights).

We learned that we can traverse (a.k.a. search) graphs in two

ways:
1- Breadth-first search (BFS) (requires a queue)
2- Depth-first search (DFS) (requires a stack)

Their complexity is same ➔ 𝜃(|𝑉| + |𝐸|

4
 In the last Lecture…(cont.)
• BFS finds a path between two nodes by taking one step down all
paths and then immediately backtracking.

• DFS finds a path between two vertices by exploring each possible

path as far as possible before backtracking.

• Some animations:
https://visualgo.net/en/dfsbfs
https://csacademy.com/lesson/breadth_first_search/
https://csacademy.com/lesson/depth_first_search/

5
 Today’s Agenda
•Greedy Graph Algorithms
•Minimum Spanning Tree Problem
• Prim’s Algorithms
• Kruskal’s Algorithms

6
Greedy Algorithms
Similar with Dynamic Programming;
◦ problems to which greedy algorithms apply have optimal
substructure.
One major difference between greedy algorithms and
dynamic programming is that:
◦ Instead of first finding optimal solutions to subproblems and
then making an informed choice,
◦ Greedy algorithms first make a “greedy” choice.
Idea: A greedy algorithm always makes the choice
that looks best at a moment. That is, it makes a
locally optimal choice in the hope that this choice
will lead to a globally optimal solution.
8
Minimum Spanning Tree (MST)
Minimum Spanning Tree (MST)
MST (cont.)
MST(cont.)
MST(cont.)
Applications of MST

Find the least expensive way to connect a set of

cities, terminals, computers, etc.

14
MST (Example)
Problem
• A town has a set of houses
and a set of roads
• A road connects 2 and only
2 houses
• A road connecting houses u and v has a repair
cost w(u, v)
Goal: Repair enough (and no more) roads such
that:
1. Everyone stays connected
i.e., can reach every house from all other houses
2. Total repair cost is minimum

16
 MST (Example) (cont.)
• A connected, undirected graph:

– Vertices = houses, Edges = roads

• A weight w(u, v) on each edge (u, v)  E

17
How to find an MST?
Let’s brainstorm
How would we design a greedy algorithm?
Idea 1:
Idea 1(cont.)

20
Idea 1(cont.)

21
Idea 1(cont.)

22
Idea 1(cont.)

23
Idea 1(cont.)

24
Idea 1(cont.)

25
Idea 1(cont.)

26
Idea 1(cont.)

27
Idea 1(cont.)

28
PRIM(V, E, w, r)
1. Q← 
2. for each u  V
3. do key[u] ← ∞
4. π[u] ← NIL
5. INSERT(Q, u)
6. DECREASE-KEY(Q, r, 0) ► key[r] ← 0
7. while Q  
8. do u ← EXTRACT-MIN(Q)
9. for each v  Adj[u]
10. do if v  Q and w(u, v) < key[v]
11. then π[v] ← u
12. DECREASE-KEY(Q, v, w(u, v))
29
Example
  
b
8
c
7
d 0  
4 9
 2  Q = {a, b, c, d, e, f, g, h, i}
a 11 i 14 e
7 6
4
VA = 
8 10
h g f Extract-MIN(Q)  a
1 2
  

4
  
8 7 key [b] = 4  [b] = a
b c d
4 9 key [h] = 8  [h] = a
 2 
a 11 i 4 14 e
8
7 6
10 4 8
h g 2
f Q = {b, c, d, e, f, g, h, i} VA = {a}
1
8  
Extract-MIN(Q)  b
30
 Example
4 
8  key [c] = 8  [c] = b
8 7
b c d
9
key [h] = 8  [h] = a - unchanged
4
 2 
8 8
a 11 i 4 14 e
7 6 Q = {c, d, e, f, g, h, i} VA = {a, b}
8 10
h g f Extract-MIN(Q)  c
1 2
8  
key [d] = 7  [d] = c
4 8 
7
8 7 key [f] = 4  [f] = c
b c d
4 2 2

9

key [i] = 2  [i] = c
a 11 i 4 14 e
8
7 6
10 7 4 8 2
h g 2
f Q = {d, e, f, g, h, i} VA = {a, b, c}
1
8  
4
Extract-MIN(Q)  i
31
 Example
4 8 7 key [h] = 7  [h] = i
8
b c
7
d key [g] = 6  [g] = i
4 9
2 2  7 46 8
a 11 i 4 14 e
Q = {d, e, f, g, h} VA = {a, b, c, i}
7 6
Extract-MIN(Q)  f
8 10
h g 2
f
1
87 
6 4
4 8 7 key [g] = 2  [g] = f
b
8
c
7
d key [d] = 7  [d] = c unchanged
9
4
2 2 10 key [e] = 10  [e] = f
a 11 i 14 e
4 7 10 2 8
7 6
8 10 Q = {d, e, g, h} VA = {a, b, c, i, f}
h g f
1
6
2
4
Extract-MIN(Q)  g
7 2
32
 Example
4 8 7 key [h] = 1  [h] = g
8 7
b c d 7 10 1
4 9
2 2 10 Q = {d, e, h} VA = {a, b, c, i, f, g}
a 11 i 14 e
7 6
4
Extract-MIN(Q)  h
8 10
h g 2
f
1
7
1 2 4 7 10
4 8 7
8 7
Q = {d, e} VA = {a, b, c, i, f, g, h}
b c d
4 9 Extract-MIN(Q)  d
2 2 10
a 11 i 4 14 e
7 6
8 10
h g 2
f
1
1 2 4
33
 Example

4 8 7
8 7
b c d
9 9
key [e] = 9  [e] = f
4
2 2 10
9
a 11 i 4 14 e
7 6 Q = {e} VA = {a, b, c, i, f, g, h, d}
8 10
h g f Extract-MIN(Q)  e
1 2
1 2 4 Q =  VA = {a, b, c, i, f, g, h, d, e}

34
 PRIM(V, E, w, r)
1. Q← 
Total time: O(VlgV + ElgV) = O(ElgV)
2. for each u  V
3. do key[u] ← ∞ O(V) if Q is implemented
as a min-heap
4. π[u] ← NIL
5. INSERT(Q, u)
O(lgV)
6. DECREASE-KEY(Q, r, 0) ► key[r] ← 0
Min-heap
Executed |V| times
7. while Q   operations:
Takes O(lgV) O(VlgV)
8. do u ← EXTRACT-MIN(Q)
Executed O(E) times total
9. for each v  Adj[u] O(ElgV)
Constant
10. do if v  Q and w(u, v) < key[v] Takes O(lgV)
11. then π[v] ← u
12. DECREASE-KEY(Q, v, w(u, v))
35
Recap: How to find an MST?
Let’s brainstorm
How would we design a greedy algorithm?
Idea 1: Prim’s Algorithm
Idea 2:

38
KRUSKAL(V, E, w)
1. A← 
2. for each vertex v  V
3. do MAKE-SET(v) O(V)

4. sort E into non-decreasing order by w O(ElgE)

5. for each (u, v) taken from the sorted list O(E)
6. do if FIND-SET(u)  FIND-SET(v)
7. then A ← A  {(u, v)}
O(lgV)
8. UNION(u, v)
9. return A
- Running time: O(V+ElgE+ElgV)=O(ElgE)
O(ElgV)
- Since E=O(V2), we have lgE=O(2lgV)=O(lgV)
67
 Kruskal’s Algorithm (Example)
1. Add (h, g) {g, h}, {a}, {b}, {c}, {d}, {e}, {f}, {i}
8 7
b c d 2. Add (c, i) {g, h}, {c, i}, {a}, {b}, {d}, {e}, {f}
4 9
2 3. Add (g, f) {g, h, f}, {c, i}, {a}, {b}, {d}, {e}
a 11 i 4 14 e 4. Add (a, b) {g, h, f}, {c, i}, {a, b}, {d}, {e}
7 6 5. Add (c, f) {g, h, f, c, i}, {a, b}, {d}, {e}
8 10
h
1
g 2
f 6. Ignore (i, g) {g, h, f, c, i}, {a, b}, {d}, {e}
7. Add (c, d) {g, h, f, c, i, d}, {a, b}, {e}
1: (h, g) 8: (a, h), (b, c) 8. Ignore (i, h) {g, h, f, c, i, d}, {a, b}, {e}
2: (c, i), (g, f) 9: (d, e) 9. Add (a, h) {g, h, f, c, i, d, a, b}, {e}
4: (a, b), (c, f) 10: (e, f) 10. Ignore (b, c) {g, h, f, c, i, d, a, b}, {e}
6: (i, g) 11: (b, h) 11. Add (d, e) {g, h, f, c, i, d, a, b, e}
7: (c, d), (i, h) 14: (d, f) 12. Ignore (e, f) {g, h, f, c, i, d, a, b, e}
{a}, {b}, {c}, {d}, {e}, {f}, {g}, {h}, {i} 13. Ignore (b, h) {g, h, f, c, i, d, a, b, e}
14. Ignore (d, f) {g, h, f, c, i, d, a, b, e}
71
72