# minimum spanning tree

(definition)

**Definition:**
A minimum-weight *tree* in a *weighted graph* which contains all of the graph's *vertices*.

**Also known as** MST, shortest spanning tree, SST.

**Generalization** (I am a kind of ...)

*spanning tree*.

**Aggregate parent** (I am a part of or used in ...)

*Christofides algorithm* (1).

**See also**
*Kruskal's algorithm*, *Prim-Jarnik algorithm*, *Boruvka's algorithm*, *Steiner tree*, *arborescence*, similar problems: *all pairs shortest path*, *traveling salesman*.

*Note:
A minimum spanning tree can be used to quickly find a near-optimal solution to the **traveling salesman* problem.

*
* The term "shortest spanning tree" may be more common in the field of operations research.

* A Steiner tree is allowed additional connection points to reduce the total length even more.*

Author: JLG

## Implementation

(C++, Pascal, Fortran, C, and Mathematica). CALGO Algorithm 613 (Fortran).
## More information

Eppstein's lecture outlining and contrasting MST algorithms.

Go to the
Dictionary of Algorithms and Data
Structures home page.

If you have suggestions, corrections, or comments, please get in touch
with Paul Black.

Entry modified 25 July 2022.

HTML page formatted Mon Jul 25 09:56:30 2022.

Cite this as:

Joseph L. Ganley, "minimum spanning tree", in
*Dictionary of Algorithms and Data Structures* [online], Paul E. Black, ed. 25 July 2022. (accessed TODAY)
Available from: https://www.nist.gov/dads/HTML/minimumSpanningTree.html