Graphs

minimum spanning tree

Given a connected, weighted, undirected graph, a minimum spanning tree (MST) is the cheapest way to connect all the vertices together. Imagine you must lay cable so that every house in a town is linked into one network, and you want the smallest total length of cable. The answer is an MST: it touches every vertex, uses no more edges than necessary, and forms a tree (V vertices joined by exactly V-1 edges, no cycles) whose total weight is as small as possible.

Two classic greedy algorithms find it. Kruskal's algorithm sorts all edges from cheapest to most expensive and adds each edge as long as it does not create a cycle, until everything is connected. Prim's algorithm grows the tree from a starting vertex, repeatedly adding the cheapest edge that reaches a vertex not yet in the tree. Both rely on the insight that you can always safely take the smallest edge crossing from the built-so-far part to the rest.

Their costs are similar: Kruskal is about O(E log E) (dominated by sorting the edges), and Prim with a priority queue is about O((V + E) log V). Note an MST minimizes total connection cost, which is a different goal from a shortest path — an MST is generally not the route giving each pair its shortest individual distance.

sort(edges.begin(), edges.end());   // by weight
for (auto [w, u, v] : edges) {
  if (find(u) != find(v)) {         // no cycle
    unite(u, v);
    total += w;                     // edge in MST
  }
}

Union-find tests cheaply whether two endpoints are already connected.

An MST exists only for connected graphs; for a disconnected graph you instead get a minimum spanning forest, one tree per component.

Also called

MSTKruskal's algorithmPrim's algorithm最小生成樹Kruskal 算法Prim 算法