最小生成树（MST）

A spanning tree of a connected graph $G=(V,E)$ is a tree that connects all elements of $V$. A weighted graph is a graph that has a monetary cost to traverse each edge. A minimal spanning tree of $G$ is then a spanning tree of $G$ that minimizes the total sum of weights.

One practical use of spanning trees is building roads. Say we have many cities that we want to connect with one another, and to connect any given pair of cities it might have a cost associated to build a road between them. Then a minimal spanning tree would be tell us the minimal cost we need to spend to do this.

Kruskal's Algorithm

Kruskal's algorithm is one way to compute a minimum spanning tree. It is a greedy algorithm, which means it takes the best option at each step. It is well-known that greedy algorithms do not always give optimal results, but in this algorithm it does give an optimal result. The algorithm is:

Sort the edges from least weight to greatest weight. At each step, choose the smallest available weight, throwing it out if it creates a cycle somewhere.

It can be shown by induction that this algorithm creates a minimal spanning tree.

Prim's Algorithm

Prim's algorithm is another greedy algorithm that solves this problem. While Kruksal's algorithm focuses on the edges, Prim's algorithm focuses on the vertices:

Start at an arbitrary vertex. Let $S$ be a list initially containing just that vertex, and of the edges connecting vertices of $S$ to vertices of $V\backslash S$, select the one of minimum weight and add the new vertex to $S$.

It can also be shown that this algorithm indeed generates a minimum spanning tree.