- 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.

- An MST is connected, contains
- Note, cycles are redundant for connectivity.

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

- (NB. redundancy may in fact be useful for reliability.)

MST . . .

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

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

- How . . .

*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
< {v _{1}}, { } >

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

- Does this | V | - 1 times.

Start with the tree < { v_{1} }, { } >.
Vertex v_{4} is closest to tree . . .

MST

v

MST

v

MST

v

MST

v

MST

Done: Minimum Spanning Tree for G.

done := {v[*] Need to store more information to recover the MST as well as its cost._{1}} --initial Tree is <{v_{1}},{}> for vertex i in V-{v_{1}} 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

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

- Suppose the algorithm chooses closest vertex v
_{c}, and edge (v_{t}, v_{c}), during an iteration.

- v
_{c}must be connected to v_{1}somehow in a final MST.

Either {v_{1}, ..., v_{t}, v_{c}} is an optimal way or there is a*cheaper way, but*

- that cannot involve any vertex, v
_{u}, not*currently*in the tree, and edge (v_{t'},v_{u}), because|(v , and_{t}, v_{c})| <= |(v_{t'}, v_{u})|

- there cannot be a cheaper edge from the (sub) tree
to v
_{c}because the algorithm picks the cheapest edge from the tree to a vertex in V-done.

- that cannot involve any vertex, v
- Termination - obvious.

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

- 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.

© L.Allison, Friday, 30-Sep-2016 09:47:57 EST www.csse.monash.edu.au/~lloyd/tilde/CSC2/CSE2304/Notes/16MST1.shtml