The LiveBoard was not working for this lecture.

MST-Kruskal pseudocode was given. This can be found in the textbook.

Running time depends on Disjoint set implementation. Is O(E alpha(E,V)) where alpha is the Ackerman inverse function and is O(E log E ).

Prim's algorithm - Edges in set A always form a single tree. Start with arbitrary root vertex r, keep growing from there, always adding edge out of tree with least weight.

Uses priority queue data structure (PQ). All vertices not in tree reside in the queue. The key of each node is minimum weight of edge connecting vertex to tree (or infinity). Keep parents in pi[v] too.

Prim's pseudocode given. This is in the textbook.

Running time depends on PQ implementation. Using heaps, we get O(v log v + E log v) = O(E log v) since connected graph.

Another data structure called the Fibonnaci heap does extract min in O(log v) and dec-key in O(1) so it gives us O(E + V logV).

Showed animations of Prim and Kruskal. They can be found in /net/ag20/softviz/polka/Samba/3158/prim and kruskal.