Connecting everything as cheaply as possible

Lay cable to connect every building on a campus. Any building can reach any other, and the total length should be as small as possible.

That is a minimum spanning tree: a subset of edges connecting every vertex, with no cycles, of the least total weight. With V vertices it always has exactly V minus 1 edges.

Kruskal

Sort every edge by weight and add them cheapest first, skipping any that would create a cycle.

def kruskal(n, edges):           # edges are (weight, u, v)
    parent = list(range(n))

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]    # path compression
            x = parent[x]
        return x

    total, used = 0, 0
    for w, u, v in sorted(edges):
        ru, rv = find(u), find(v)
        if ru != rv:              # different components, no cycle
            parent[ru] = rv
            total += w
            used += 1
    return total if used == n - 1 else None   # None: not connected

O(E log E), dominated by the sort. The cycle check is a union find, which is the next page and the only reason this is efficient.

Prim

Grow a single tree from one vertex, repeatedly taking the cheapest edge leaving it. With a heap that is O((V + E) log V), and the structure is very close to Dijkstra.

The one line of difference is worth seeing:

Dijkstra:  if dist[u] + weight < dist[v]     # distance from the source
Prim:      if weight < dist[v]               # distance from the tree

Dijkstra accumulates the path cost. Prim only cares about the edge into the tree. Two famous algorithms separated by one addition.

Why greedy is correct here

Take any cut splitting the vertices in two. The lightest edge crossing it must be in some minimum spanning tree: if a tree omits it, adding it creates a cycle that must cross the cut again, and swapping that heavier edge out gives a tree no worse.

Both algorithms are applications of that one fact, which is why both work despite looking different.

Where it is used

Network and utility layout, which is the original problem. Clustering, by building the tree and removing the k most expensive edges. Image segmentation. Approximation algorithms for the travelling salesman problem.