What is a Spanning Tree:

https://www.youtube.com/watch?v=fXvQFE5siAI

It is a connected graph using all the vertices with no cycles.

What is a MST?

We want t find a subset of E with minimum total weigth/length that connect all the nodes/vertices into a tree.

The Generic MST Algorithm

Generic-MST(G,w)
A= ∅
whileAdoes not form a spanning tree
fine an edge (u,v) that is safe forA
A=A∪ {(u,v)}
returnA

Loop invariants:

Finding a "safe" edge

How do we find a safe edge?
One must exist, since we are working with a connected graph, andAis at all times a part of an MST.
Definition: a cut (S,V-S) of an undirected graphG= (V,E) is a partition ofV.
Definition: an edge (u,v) crosses the cut (S,V-S) if one of its endpoints is inSand the other inV.
Definition: a cutrespectsa setAof edges if no edge inAcrosses the cut.
Definition: An edge is alight edgecrossing a cut if its weight is minimum among all edges crossing the cut. Uniqueness is not required.