[Subject home], [FAQ], [progress],   Bib', Alg's,  C , Java - L.A., Wednesday, 25-May-2016 19:07:54 EST
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

Graph:

-

MST . . .

. . . MST
-

Prim's MST Algorithm

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:

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

Prepare: Kruskal's MST algorithm.
© L.Allison, Wednesday, 25-May-2016 19:07:54 EST www.csse.monash.edu.au/~lloyd/tilde/CSC2/CSE2304/Notes/16MST1.shtml
Computer Science, Software Engineering, Science (Computer Science).