最小生成树是在连通无向带权图中选取能连通全部顶点且不形成回路的一组边，并使边权总和最小。常用算法包括 Kruskal 和 Prim：Kruskal 按边权从小到大选边，并用连通分量或并查集判断是否成环；Prim 从某个顶点出发，每次选择连接已加入顶点集合与未加入顶点集合的最小权边。解题时不能把所有局部较小的边简单相加，关键是覆盖全部顶点、边数为顶点数减一且不能形成回路。它解决的是“用最低总代价连通所有节点”的网络设计问题，常见于布线、管网、通信链路选型等场景。与最短路径不同，最小生成树关注整体连通代价，不关心某两个顶点之间路径是否最短；若图不连通，则只能得到各连通分量的最小生成森林。