constituents

an undirected, conected, weighted graph

requirements

• a spanning tree is a tree that touches all of the vericies (i.e. a graph with no cycles)
• minimum spanning tree is a tree that connects all of the vertices with minimum edge cost

algorithm

Kruskal’s Algorithm

“smallest edge that doesn’t make a cycle”

Sort the edges in \(E\) by non-decreasing weight. For everything in E in sorted order, if adding E to MST won’t cause a cycle, then add E to MST. Then return.

Insight: when we add an edge, me merge two trees

Sort E by weight by weight in non-decreasing order
MST = {}
for v in V:
    makeSet(v)

for u,v in E:
    # append if u and v are not in the same tree, which is how you detect cycles
    if find(u) != find(v):
        MST.append((u,v))
        union((u,v))

return MST

This runs also in \(O\qty(m \log m) = O\qty(m\log \qty(n))\) since trees has at most \(n-1\) edges. This works if we consider the tree that we are about to merge \(T_1, T_2\); call \(T_1\) one side of the cut \(V - T_1\) the other (they are disconnected as \(S\)).

disjoint-set union

1. makeSet(u) (creates a set u)
2. find(u) (return the set u is in)
3. union(u,v) (merge the two sets

Prim’s Algorithm

“start with some known tree and add the shortest edge”

1. start somewhere random
2. greedily add the smallest-weighted edge from there
3. repeat

s = some_edge(G)
MST = {(s,u) be the lightest edge in G}

visited = {s,u}

while |visited| < |V|:
    find lightest edge x,v such that x is visited and v is not
    add (x,v) to MST
    add v to visited

return mst

Proof: apply lightest edge lemma, your cut is the visited and non-visited edge (which does respect our edge set). We are indeed adding the lightest edge, so there. How do we make this fast?

To make this fast:

1. every vertex has a “key” (minimum distance of x from the growing tree) and a “parent” (the vertex from which the key came)
2. until all vertices are reached
   • activate the unreached vertex u with the smallest key
   • for each u’s unreached neighbors…
     • k(v) = min(k(v), weight(u,v))
     • if k(v) is updated, p(v) = u
3. mark u as reached, add (p(u), u) to minimum spanning tree

To implement the minimum structure, we need to implement like in Dijikstra, with a heap or a RBT.

This runs in \(O\qty(m\qty(\log n))\) like in Dijikstra’s Algorithm, which is \(O\qty(\qty(n+m) \log\qty(n))\), and in a tree since there are \(n-1\) edges, then that gives \(O\qty(m\log \qty(n))\).

additional information

uniqueness

use cases

• connecting cities with roads / electricity / telephone
• cluster analysis for generitic distance
• image segmentation

cut

A cut in a graph partitions the vertices into two parts. We say an edge “crosses the cut” if it goes between two nodes from different cuts.

respect

We say a cut respects \(S \subseteq E\) if no edges in \(S\) cross the cut.

light

We say an edge crossing a cut is called light if it has the smallest weight of any edge crossing the cut.

lightest edge lemma