最小生成森林
不连通带权无向图中,每个连通块各取一棵 MST 得到的最小权森林;连通时退化为 MST。标签 图论 / 生成树 / 最小生成森林
定义
给定带权无向图 (不要求连通)。生成森林是 的一个无环子图,包含全部顶点,且每个连通块内是一棵 树。
最小生成森林(Minimum Spanning Forest, MSF)是所有生成森林中边权和最小的那一个。
等价地说:对 的每个连通块分别求最小生成树,再把它们并起来。
与最小生成树的关系
- 图连通时,生成森林就是生成树,MSF 就是 MST。
- 图不连通时,不存在生成树,但一定存在生成森林。
- 因此“图不连通”不是无解,而是要求 MSF 而不是 MST。
边数与存在性
设图有 个顶点、 个连通块。任意生成森林恰好有 条边:
- 每个连通块内是一棵树,边数 = 点数 - 1。
- 对所有连通块求和,得到 。
所以 MSF 的边数是固定的;若算法结束时边数少于 ,说明漏掉了某些连通块。
最优性的分解
不同连通块之间没有边,选择互不影响。因此:
- 全局 MSF 的权值 = 各连通块 MST 权值之和。
- 在每个连通块内独立应用割性质 / 环性质即可。
这也是为什么 Kruskal 在不要求最终连通时,天然会得到 MSF。
求解细节见 Kruskal、Prim、Borůvka 页面。
常见误解
- 认为不连通图没有最小生成森林:它有,只是没有生成树。
- 认为 MSF 必须包含 条边:那是连通图;一般情况是 条。
- 认为 MSF 唯一:和 MST 一样,边权相同时可能不唯一。
- 认为 MSF 会把不同连通块连起来:不会,连通块之间没有路径。