minimum_spanning_tree

最小生成树（Minimum Spanning Tree，MST）是图论中的一个概念，它是连通图中所有顶点的集合，且这个子图的所有边权值之和最小。最小生成树有许多实际应用，如网络设计、电路设计等。常用的最小生成树算法有Prim算法和Kruskal算法。Prim算法以起始点为中心向外层层扩展，直到扩展到全部顶点；Kruskal算法按照边的权值从小到大的顺序选择边，并通过并查集判断是否有环，直到全部顶点都被包含进来。最小生成树具有许多重要的性质，如唯一性、最优性和极小性。