[Subject home], [FAQ], [progress],   Bib', Alg's,  C , Java - L.A., Sunday, 28-Nov-2021 04:45:08 AEDT
Instructions: Topics discussed in these lecture notes are examinable unless otherwise indicated. You need to follow instructions, take more notes & draw diagrams especially as [indicated] or as done in lectures, work through examples, and do extra reading. Hyper-links not in [square brackets] are mainly for revision, for further reading, and for lecturers of the subject.

## Graphs:   Min' Spanning Tree (Prim):     Introduction

• Saw various kinds of Graph and examples,   now . . .

• Minimum spanning tree (MST) of a weighted undirected graph, G.

• An MST is connected, contains all vertices and a subset of edges of G.

• Note, cycles are redundant for connectivity.

• Spanning tree is non-redundant, cheaper.  Minimum one = cheapest.

• (NB. redundancy may in fact be useful for reliability.)
Graph: MST . . .

. . . MST • Minimum Spanning Tree in red,   NB. not necessarily unique.

• Connected, no cycles, minimal (cheapest, lightest). Can you do better?

• How . . .

### Prim's MST Algorithm

• Very similar to Dijkstra's   s' s' shortest paths algorithm

which was optimising [what_______________________?] criterion.

• Also a dynamic programming, greedy algorithm.

• Prim's MST alg' starts with a small tree < {v1}, { } >

• It iterates, adding the "undone" vertex that is closest to the tree.

• Does this   | V | - 1   times.
Graph: Start with the tree  < { v1 }, { } >.   Vertex v4 is closest to tree . . .

MST v3 is closest to tree . . .
MST v2 and v5 are closest to tree,   pick v5, say . . .
MST v6 is closest to tree . . .
MST v2 is closest (and only remaining) vertex . . .
MST Done: Minimum Spanning Tree for G.
[lecturer: run demo'; class: take notes!]
```done := {v1}   --initial Tree is <{v1},{}>

for vertex i in V-{v1}
T[i] := E[1,i]     --direct edges else "infinity"    [*]
end for

loop |V|-1 times
-- INV: {T[v]|v in done} represents a min' spanning Tree
-- of the nodes in done and {T[u]|u not in done} contains
-- the shortest known distances from the (sub-)spanning Tree
-- to such vertices u.

find closest vertex to (sub-)spanning Tree in V - done;

done +:= {closest};
add `closest' and `edge T[closest]' to (sub-)spanning Tree;

for vertex j in V - done
T[j] := min(T[j],   --update knowledge on paths,
E[closest,j])      --perhaps better? [*]
end for
end loop -- run demo',  cf. Dijkstra's

```
[*] Need to store more information to recover the MST as well as its cost.

### Proof of Prim's MST algorithm:

• The outer loop invariant is true initially when 'done' contains one vertex.

• Suppose the algorithm chooses closest vertex vc, and edge (vt, vc), during an iteration.

• vc must be connected to v1 somehow in a final MST.
Either {v1, ..., vt, vc} is an optimal way or there is a cheaper way, but

• that cannot involve any vertex, vu, not currently in the tree, and edge (vt',vu), because |(vt, vc)| <= |(vt', vu)|, and

• there cannot be a cheaper edge from the (sub) tree to vc because the algorithm picks the cheapest edge from the tree to a vertex in V-done.

So it is optimal.

• Termination - obvious.

Hint: A sub-tree of a (partial) MST must itself be a MST of those vertices that it spans.

## Graphs:   Min' Spanning Tree (Prim):   Summary

• Prims' algorithm takes O( | V |2 )-time.

• Very similar to Dijkstra's single-source shortest paths algorithm,

• greedy, dynamic programming,

• subtly different optimisation criterion to Dijkstra's.

• Homework: compare Dijkstra's (paths) algorithm and Prim's MST algorithm; make sure you understand their similarities and their differences.
Prepare: Kruskal's MST algorithm.
© L.Allison, Sunday, 28-Nov-2021 04:45:08 AEDT users.monash.edu.au/~lloyd/tilde/CSC2/CSE2304/Notes/16MST1.shtml
Computer Science, Software Engineering, Science (Computer Science).