最小生成树（Minimum Spanning Tree） 是在一个无向连通加权图中一个联通了所有节点，并且所有边的权重的和是所有连通方案中最小的，无环的一个节点和边组成的子集，因为无环，所有这个子集也是一个树，所以叫最小生成树。
对于一个无向非连通（不是所有的节点都有路径相连）加权图，每个连通的分量（子图）中都有自己的最小生成树，所有的最小生成树的合集被称为最小生成森林。
对于给定的图，求解最小生成树的算法主要有两种：
Kruskal 算法
按照边的权重顺序（从小到大）将边加入生成树中，但是若加入该边会与生成树形成环则不加入该边。直到树中含有 条边为止。这些边组成的就是该图的最小生成树。
Prime 算法
每一步都会为一棵生长中的树添加一条边，该树最开始只有一个顶点，然后会添加 个边。每次总是添加生长中的树和树中除该生长的树以外的部分形成的切分的具有最小权值的横切边。