最小顶点覆盖问题的精确解法（基于树形动态规划）
字数 2990 2025-12-11 06:01:45

好的，我们来看一个你列表中尚未出现过的经典图论算法题目。

最小顶点覆盖问题的精确解法（基于树形动态规划）

题目描述

给定一个 无向树（即一个无环且连通的无向图，有 n 个顶点和 n-1 条边），我们需要找到它的一个 最小顶点覆盖。

最小顶点覆盖 的定义是：图中的一组顶点构成的集合 C，使得图中的每一条边都至少有一个端点属于 C。而“最小”是指这个集合 C 的顶点数量是所有顶点覆盖中最少的。

要求我们设计一个算法，精确地（而非近似地）求出这棵树的最小顶点覆盖的大小，并能够重构出这个覆盖集合本身。

核心难点与解题思路

对于任意图，最小顶点覆盖是一个NP-hard问题。但题目特别指出图是一棵树。树的结构非常简单（无环），这使我们能够利用其递归性质。核心思路是使用树形动态规划。

我们可以任意选择一个根节点（例如节点0），把无根树转化为一棵有根树。然后从叶子节点向根节点自底向上进行状态计算。对于每个节点，我们需要考虑它是否被选入覆盖集合，而它的状态会受到其子节点状态的影响。

逐步解题过程

步骤1：定义动态规划状态

我们为树中的每个节点 u 定义两个DP状态值：

  • dp[u][0]: 表示在以节点 u 为根的子树中，当节点 u 自身不被选入顶点覆盖集合时，这棵子树所需的最小顶点覆盖大小。
  • dp[u][1]: 表示在以节点 u 为根的子树中，当节点 u 自身被选入顶点覆盖集合时，这棵子树所需的最小顶点覆盖大小。

我们的最终目标是求出 min(dp[root][0], dp[root][1])。

步骤2：建立状态转移方程

我们以节点 u 为当前计算的节点，假设它有子节点 v1, v2, ..., vk。我们需要根据子节点的状态来计算 u 的状态。

  1. 情况 dp[u][1] (u被选入覆盖)：

    • 如果 u 已经在覆盖集合里，那么所有与 u 相连的边（包括连接其子节点的边）都已经被覆盖。
    • 因此，对于 u 的每个子节点 v，它可以自由选择是否进入覆盖集合，我们只需要选择对以 v 为根的子树最有利（即覆盖数最小）的那个选项。
    • 状态转移方程为：
      dp[u][1] = 1 + sum( min(dp[v][0], dp[v][1]) ) for each child v of u
      • 公式中的 1 代表节点 u 本身被选中。
      • min(dp[v][0], dp[v][1]) 表示对于子节点 v 的子树，我们选择最优的覆盖方案。

  2. 情况 dp[u][0] (u不被选入覆盖)：

    • 如果 u 不在覆盖集合里，那么为了覆盖连接 u 和其子节点 v 的边 (u, v)，子节点 v 必须被选入覆盖集合。
    • 否则，边 (u, v) 将没有被覆盖，违反了顶点覆盖的定义。
    • 因此，状态转移方程为：
      dp[u][0] = sum( dp[v][1] ) for each child v of u

步骤3：确定初始条件（叶子节点）

对于叶子节点（没有子节点的节点）：

  • dp[leaf][0] = 0：如果叶子不被选，它没有子节点需要覆盖，所以其子树覆盖大小为0。
  • dp[leaf][1] = 1：如果叶子被选，它自身计入覆盖，所以大小为1。

步骤4：算法执行流程（自底向上计算）

  1. 建树与选根：将给定的无向树用邻接表存储。任意选择一个节点（如节点0）作为根节点。
  2. 执行DFS：从根节点开始进行深度优先搜索（DFS）。DFS会递归地访问所有子节点，直到叶子节点。
  3. 后序计算：在DFS的回溯阶段（即处理完所有子节点后），根据上述转移方程计算当前节点 u 的 dp[u][0] 和 dp[u][1]。
  4. 得到答案：当DFS从根节点完全返回时，答案就是 min(dp[root][0], dp[root][1])。

步骤5：重构最小顶点覆盖集合

为了不仅知道大小，还要知道具体哪些节点在覆盖中，我们需要在动态规划的过程中记录“选择”。

  • 我们可以使用一个辅助的布尔数组 inCover[]。
  • 在进行最终决策 min(dp[root][0], dp[root][1]) 时，我们可以决定根节点是否应被加入覆盖。
  • 然后，我们进行第二次DFS来填充 inCover[]。从根节点开始：
    • 如果当前节点 u 被标记为应在覆盖中（inCover[u] = true），那么对于它的每个子节点 v，我们可以选择使得 dp[v] 更小的方案（即 min(dp[v][0], dp[v][1])），并相应地标记 v。
    • 如果当前节点 u 不在覆盖中（inCover[u] = false），那么根据转移方程，它的所有子节点 v 必须在覆盖中（inCover[v] = true）。

复杂度分析

  • 时间复杂度：O(n)。我们对树进行了两次DFS遍历，每个节点和每条边都被访问常数次。
  • 空间复杂度：O(n)。用于存储邻接表、DP数组和记录选择的数组。

示例演示

考虑一棵简单的树：

   0
  / \
 1   2
    / \
   3   4

  1. 以节点0为根。

  2. 自底向上计算：

    • 节点1（叶子）：dp[1][0]=0, dp[1][1]=1
    • 节点3（叶子）：dp[3][0]=0, dp[3][1]=1
    • 节点4（叶子）：dp[4][0]=0, dp[4][1]=1
    • 节点2：有子节点3和4。
      • dp[2][1] = 1 + min(dp[3][0],dp[3][1]) + min(dp[4][0],dp[4][1]) = 1 + 0 + 0 = 1
      • dp[2][0] = dp[3][1] + dp[4][1] = 1 + 1 = 2
    • 节点0：有子节点1和2。
      • dp[0][1] = 1 + min(dp[1][0],dp[1][1]) + min(dp[2][0],dp[2][1]) = 1 + 0 + 1 = 2
      • dp[0][0] = dp[1][1] + dp[2][1] = 1 + 1 = 2

  3. 最终答案：min(dp[0][0], dp[0][1]) = 2。

  4. 重构覆盖（假设我们选择让根节点0进入覆盖，因为 dp[0][1]=2 是可选方案之一）：

    • inCover[0] = true。
    • 对于子节点1：从 min(0, 1) 中选择更小的方案，即 dp[1][0]=0，所以 inCover[1] = false。
    • 对于子节点2：从 min(2, 1) 中选择更小的方案，即 dp[2][1]=1，所以 inCover[2] = true。
    • 对于节点2（在覆盖中），看其子节点：
      • 子节点3：从 min(0, 1) 中选， inCover[3] = false。
      • 子节点4：从 min(0, 1) 中选， inCover[4] = false。
    • 最终覆盖集合是 {0, 2}，大小为2。验证：所有边 (0,1), (0,2), (2,3), (2,4) 都至少有一个端点在集合内。

通过这个树形DP方法，我们高效且准确地解决了树上的最小顶点覆盖问题。

好的，我们来看一个你列表中尚未出现过的经典图论算法题目。 最小顶点覆盖问题的精确解法（基于树形动态规划） 题目描述 给定一个 无向树 （即一个无环且连通的无向图，有 n 个顶点和 n-1 条边），我们需要找到它的一个 最小顶点覆盖 。 最小顶点覆盖 的定义是：图中的一组顶点构成的集合 C ，使得图中的每一条边都至少有一个端点属于 C 。而“最小”是指这个集合 C 的顶点数量是所有顶点覆盖中最少的。 要求我们设计一个算法， 精确地 （而非近似地）求出这棵树的最小顶点覆盖的大小，并能够重构出这个覆盖集合本身。 核心难点与解题思路 对于任意图，最小顶点覆盖是一个NP-hard问题。但题目特别指出图是一棵 树 。树的结构非常简单（无环），这使我们能够利用其递归性质。核心思路是使用 树形动态规划 。 我们可以任意选择一个根节点（例如节点0），把无根树转化为一棵有根树。然后从叶子节点向根节点 自底向上 进行状态计算。对于每个节点，我们需要考虑它是否被选入覆盖集合，而它的状态会受到其子节点状态的影响。 逐步解题过程 步骤1：定义动态规划状态 我们为树中的每个节点 u 定义两个DP状态值： dp[u][0] : 表示在以节点 u 为根的子树中，当 节点 u 自身不被选入 顶点覆盖集合时，这棵子树所需的最小顶点覆盖大小。 dp[u][1] : 表示在以节点 u 为根的子树中，当 节点 u 自身被选入 顶点覆盖集合时，这棵子树所需的最小顶点覆盖大小。 我们的最终目标是求出 min(dp[root][0], dp[root][1]) 。 步骤2：建立状态转移方程 我们以节点 u 为当前计算的节点，假设它有子节点 v1, v2, ..., vk 。我们需要根据子节点的状态来计算 u 的状态。 情况 dp[u][1] (u被选入覆盖) ： 如果 u 已经在覆盖集合里，那么所有与 u 相连的边（包括连接其子节点的边）都已经被覆盖。 因此，对于 u 的每个子节点 v ，它可以 自由选择 是否进入覆盖集合，我们只需要选择对以 v 为根的子树最有利（即覆盖数最小）的那个选项。 状态转移方程为： dp[u][1] = 1 + sum( min(dp[v][0], dp[v][1]) ) for each child v of u 公式中的 1 代表节点 u 本身被选中。 min(dp[v][0], dp[v][1]) 表示对于子节点 v 的子树，我们选择最优的覆盖方案。 情况 dp[u][0] (u不被选入覆盖) ： 如果 u 不在覆盖集合里，那么为了覆盖连接 u 和其子节点 v 的边 (u, v) ， 子节点 v 必须被选入覆盖集合 。 否则，边 (u, v) 将没有被覆盖，违反了顶点覆盖的定义。 因此，状态转移方程为： dp[u][0] = sum( dp[v][1] ) for each child v of u 步骤3：确定初始条件（叶子节点） 对于叶子节点（没有子节点的节点）： dp[leaf][0] = 0 ：如果叶子不被选，它没有子节点需要覆盖，所以其子树覆盖大小为0。 dp[leaf][1] = 1 ：如果叶子被选，它自身计入覆盖，所以大小为1。 步骤4：算法执行流程（自底向上计算） 建树与选根 ：将给定的无向树用邻接表存储。任意选择一个节点（如节点0）作为根节点。 执行DFS ：从根节点开始进行深度优先搜索（DFS）。DFS会递归地访问所有子节点，直到叶子节点。 后序计算 ：在DFS的 回溯 阶段（即处理完所有子节点后），根据上述转移方程计算当前节点 u 的 dp[u][0] 和 dp[u][1] 。 得到答案 ：当DFS从根节点完全返回时，答案就是 min(dp[root][0], dp[root][1]) 。 步骤5：重构最小顶点覆盖集合 为了不仅知道大小，还要知道具体哪些节点在覆盖中，我们需要在动态规划的过程中记录“选择”。 我们可以使用一个辅助的布尔数组 inCover[] 。 在进行最终决策 min(dp[root][0], dp[root][1]) 时，我们可以决定根节点是否应被加入覆盖。 然后，我们进行第二次DFS来填充 inCover[] 。从根节点开始： 如果当前节点 u 被标记为应在覆盖中（ inCover[u] = true ），那么对于它的每个子节点 v ，我们可以选择使得 dp[v] 更小的方案（即 min(dp[v][0], dp[v][1]) ），并相应地标记 v 。 如果当前节点 u 不在覆盖中（ inCover[u] = false ），那么根据转移方程，它的所有子节点 v 必须 在覆盖中（ inCover[v] = true ）。 复杂度分析 时间复杂度：O(n)。我们对树进行了两次DFS遍历，每个节点和每条边都被访问常数次。 空间复杂度：O(n)。用于存储邻接表、DP数组和记录选择的数组。 示例演示 考虑一棵简单的树： 以节点0为根。 自底向上计算： 节点1（叶子）： dp[1][0]=0 , dp[1][1]=1 节点3（叶子）： dp[3][0]=0 , dp[3][1]=1 节点4（叶子）： dp[4][0]=0 , dp[4][1]=1 节点2：有子节点3和4。 dp[2][1] = 1 + min(dp[3][0],dp[3][1]) + min(dp[4][0],dp[4][1]) = 1 + 0 + 0 = 1 dp[2][0] = dp[3][1] + dp[4][1] = 1 + 1 = 2 节点0：有子节点1和2。 dp[0][1] = 1 + min(dp[1][0],dp[1][1]) + min(dp[2][0],dp[2][1]) = 1 + 0 + 1 = 2 dp[0][0] = dp[1][1] + dp[2][1] = 1 + 1 = 2 最终答案： min(dp[0][0], dp[0][1]) = 2 。 重构覆盖（假设我们选择让根节点0进入覆盖，因为 dp[0][1]=2 是可选方案之一）： inCover[0] = true 。 对于子节点1：从 min(0, 1) 中选择更小的方案，即 dp[1][0]=0 ，所以 inCover[1] = false 。 对于子节点2：从 min(2, 1) 中选择更小的方案，即 dp[2][1]=1 ，所以 inCover[2] = true 。 对于节点2（在覆盖中），看其子节点： 子节点3：从 min(0, 1) 中选， inCover[3] = false 。 子节点4：从 min(0, 1) 中选， inCover[4] = false 。 最终覆盖集合是 {0, 2} ，大小为2。验证：所有边 (0,1) , (0,2) , (2,3) , (2,4) 都至少有一个端点在集合内。 通过这个树形DP方法，我们高效且准确地解决了树上的最小顶点覆盖问题。