https://algs4.cs.princeton.edu/43mst/

Kruskal's algorithm is more time efficient than Prim's.

Cut Property

Def. A cut in a graph is a partition of its vertices into two (nonempty) sets.

Def. A crossing edge connects a vertex in one set with a vertex in the other.

Cut property. Given any cut, the crossing edge of min weight is in the MST.

Greedy algorithm: find min weight edges in all cuts.

Kruskal's algorithm

Consider edges in ascending order of weight

• Add next edge to tree T unless doing so would create a cycle. Union-find

In essence, Kruskal's algorithm is a special case of the greedy MST algorithm

Union-find: O(logV)

Total: V(log*V) log*V <= 5 in this universe

Prim's algorithm

Prim is also a special case of the greedy MST algorithm.

Lazy Prim's algorithm: O(ElogE)

1. Start with vertex 0 and greedily grow tree T.
2. Add to T the min weight edge with exactly one endpoint in T.
3. Repeat until V - 1 edges.

Eager Prim's algorithm: O(ElogV)

Maintain a PQ of vertices connected by an edge to T, where priority of vertex v = weight of the shortest edge connecting v to T. Update priority queue by considering all edges e = v-x incident to v

• ignore if x is already in T
• add x to priority queue is not already on it
• DECREASE priority of x if v-x becomes shortest edge connecting x to T (hash heap/indexed PQ)

Exercises

Bottleneck minimum spanning tree. Given a connected edge-weighted graph, design an efficient algorithm to find a minimum bottleneck spanning tree. The bottleneck capacity of a spanning tree is the weights of its largest edge. A minimum bottleneck spanning tree is a spanning tree of minimum bottleneck capacity.

Is an edge in a MST. Given an edge-weighted graph G and an edge e, design a linear-time algorithm to determine whether e appears in some MST of G.

Note: Since your algorithm must take linear time in the worst case, you cannot afford to compute the MST itself.

Find some cuts?

Minimum-weight feedback edge set. A feedback edge set of a graph is a subset of edges that contains at least one edge from every cycle in the graph. If the edges of a feedback edge set are removed, the resulting graph is acyclic. Given an edge-weighted graph, design an efficient algorithm to find a feedback edge set of minimum weight. Assume the edge weights are positive.