最小生成森林

不连通带权无向图中,每个连通块各取一棵 MST 得到的最小权森林;连通时退化为 MST。

标签 图论 / 生成树 / 最小生成森林

定义

给定带权无向图 𝐺=(𝑉,𝐸)(不要求连通)。生成森林是 𝐺 的一个无环子图,包含全部顶点,且每个连通块内是一棵 树。

最小生成森林(Minimum Spanning Forest, MSF)是所有生成森林中边权和最小的那一个。

等价地说:对 𝐺 的每个连通块分别求最小生成树,再把它们并起来。

与最小生成树的关系

  • 图连通时,生成森林就是生成树,MSF 就是 MST。
  • 图不连通时,不存在生成树,但一定存在生成森林。
  • 因此“图不连通”不是无解,而是要求 MSF 而不是 MST。

边数与存在性

设图有 𝑛 个顶点、𝑐 个连通块。任意生成森林恰好有 𝑛−𝑐 条边:

  • 每个连通块内是一棵树,边数 = 点数 - 1。
  • 对所有连通块求和,得到 𝑛−𝑐。

所以 MSF 的边数是固定的;若算法结束时边数少于 𝑛−𝑐,说明漏掉了某些连通块。

最优性的分解

不同连通块之间没有边,选择互不影响。因此:

  • 全局 MSF 的权值 = 各连通块 MST 权值之和。
  • 在每个连通块内独立应用割性质 / 环性质即可。

这也是为什么 Kruskal 在不要求最终连通时,天然会得到 MSF。

求解细节见 Kruskal、Prim、Borůvka 页面。

常见误解

  • 认为不连通图没有最小生成森林:它有,只是没有生成树。
  • 认为 MSF 必须包含 𝑛−1 条边:那是连通图;一般情况是 𝑛−𝑐 条。
  • 认为 MSF 唯一:和 MST 一样,边权相同时可能不唯一。
  • 认为 MSF 会把不同连通块连起来:不会,连通块之间没有路径。
源码位置