最小生成树（Minimum Spanning Tree，简称MST）是图论中的一个重要概念。它指的是在一个连通加权无向图中，找到一棵包含所有顶点的树，并且这棵树的边的权重之和是所有可能的生成树中最小的。
最小生成树的性质包括：
包含所有顶点：
最小生成树必须包含原图中的所有顶点。
边的权重和最小：
最小生成树的边的权重之和是所有生成树中最小的。
构成一棵树：
最小生成树是一棵树，因此它包含n-1条边，并且是连通的。
常见的求解最小生成树的算法有：
Kruskal算法：
通过不断选择权重最小的边，并利用并查集（Union-Find）数据结构来避免形成回路，直到所有顶点都被包含在树中。
Prim算法：
从一个顶点开始，逐步扩展生成树，每次选择与当前生成树连接且权重最小的边，直到所有顶点都被包含在树中。
在实际应用中，最小生成树的概念被广泛应用于网络设计、路径规划、资源分配等领域，以寻求最优解。例如，在有线电视电缆的架设中，通过求解最小生成树可以使得布线成本最低。