File MinimumSpanningTree.h

↰ Parent directory (ADS/graph)

The minimum spanning tree of an unoriented connected graph with weights on the edges (section 14.3): a tree on all the nodes, of n - 1 edges, of least total weight.

Definition (ADS/graph/MinimumSpanningTree.h)

Detailed Description

Both algorithms are greedy, and correct by the Teorema 14.1: if A is part of a minimum spanning tree and no edge of A crosses the cut ( S , V - S ), then the lightest edge across it can be added to A.

  • kruskal() scans the edges by increasing weight and keeps one if its ends are in two components of the forest, an MFSET with the rank and the compression of the paths: O( m log n ) for the sort and almost O( m ) for the rest; it stops after n - 1 edges. With integer weights in [ 0 , k ) the edges are sorted by Counting Sort, O( m + n + k ) (exercise 14.2).

  • prim() grows the tree from a root r, adding the lightest edge that leaves it, the nodes in a priority queue by the weight of their lightest edge to the tree: O( m log n ) with a binary heap, O( n^2 ) with an unsorted list, better on dense graphs, and O( m + n log n ) with a Fibonacci heap (exercise 14.4).

A graph that is not connected gives a minimum spanning forest by kruskal(), and the tree of the component of r by prim(). Both take their structure as well: kruskal() any MFSET with merge() [see Mergeable], prim() any priority queue of section 10.1, whose priority may be the pair ( weight , node ) so that every queue gives the same tree with the same counts [see FrontierCounts, MergeCounts].

The contracts [see File Contract.h]: the graph is unoriented; the edges given to kruskal() join nodes in [ 0 , n ), with weights in [ 0 , k ) when k > 0; prim() starts from a node, with a priority queue as frontier. At the level of the audits the result is a minimum spanning forest, which isMinimumSpanningForest() checks by the property of the cycles: a spanning forest is minimum if and only if no edge out of it weighs less than an edge of the path of the forest between its ends. The functions are defined in MinimumSpanningTree.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, section 14.3, https://algoritmicamente.it/materiali/libro/capitoli/cap14.pdf

    1. Kruskal, On the shortest spanning subtree of a graph and the traveling salesman problem, Proceedings of the American Mathematical Society 7(1), 48-50, 1956, doi:10.1090/S0002-9939-1956-0078686-7

    1. Prim, Shortest connection networks and some generalizations, Bell System Technical Journal 36(6), 1389-1401, 1957, doi:10.1002/j.1538-7305.1957.tb01515.x

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Classes

Functions