---
tag: 0JW7KT6PQW
kind: concept
name: Minimum spanning tree
msc: [05C05]
sources:
  - url: https://en.wikipedia.org/wiki/Minimum_spanning_tree
    locator: lead section
same_as:
  wikidata: Q240464
  wikipedia: Minimum spanning tree
---

## Summary

A minimum spanning tree of a weighted connected graph is a spanning tree of least total weight. It is a classical problem of combinatorial optimization, solved by greedy algorithms. The node [[minimum spanning tree|0Z367CGNRM]] gives the precise definition.