最小顶点覆盖
最小顶点覆盖是一个经典的图形问题。比方说，在一个城市，我们有几条连接几个点的道路。让我们使用边和使用节点的点来表示道路。我们来看两个示例图：
https://i.stack.imgur.com/7n7bv.jpg
我们想在某些方面设置守望者。守望者可以保护连接到该点的所有道路。问题是，覆盖所有道路所需的最小守望人员是多少？如果我们在节点 A ， B ， H ， I 和 J 设置守望者，我们可以覆盖所有道路。
https://i.stack.imgur.com/ADM8O.jpg
这是我们的最佳解决方案。我们至少需要 5 名守望者才能守护整个城市。怎么判断这个？
首先，我们需要理解这是一个 NP 难问题，即问题没有多项式时间解决方案。但是如果图形是树，那意味着如果它有 （n-1）个节点，其中 n 是边数，并且图中没有循环，我们可以使用动态编程来解决它。
https://i.stack.imgur.com/YvGHM.jpg
要构建 DP 解决方案，我们需要遵循两个策略：
- 如果节点中没有守望者，则连接到它的所有节点都必须有守望者，否则所有道路都不会被覆盖。如果 U 和 v 连接和 U 没有任何守望者，那么 v 必须有一个守望者。
- 如果节点中有守望者，则与其连接的不同节点可能有也可能没有守望者。这意味着没有必要有一个守望者，但它可能是有益的。如果 U 和 v 连接和 U 有守望，我们会检查，发现其上是对我们有利的：
- 在 v 。中设置守望者
- 不在 v 中设置守望者。
让我们定义一个递归函数，其中 state 是我们当前的节点，是否有守望者。这里：
F(u,1) = Currently we're in 'u' node and there is a watchman in this node.
F(u,0) = Currently we're in 'u' node and there is no watchman in this node.
该函数将返回剩余节点中的守望者数量。
我们来看一个示例树：
https://i.stack.imgur.com/rka2p.jpg
我们可以很容易地说，如果我们不把守望者放在节点 A 上，我们就必须把守望者放在节点 B ， C 和 D 上。我们可以推断：
F(A,0) = F(B,1) + F(C,1) + F(D,1) + 0
如果我们不将守望者放在节点 **A 中，**它会返回所需的守望人数。我们最后添加了 0 ，因为我们没有在当前节点中设置任何守望者。
现在 F(A,1) 意味着，我们在节点 A 中设置了守望者。为此，我们可以在所有连接的节点中设置看门人，也可以不设置。我们将为我们提供最少数量的守望者。
F(A,1) = min(F(B,0), F(B,1) + min(F(C,0), F(C,1)) + min(F(D,0), F(D,1)) + 1
我们通过设置而不是在每个节点上设置守望者并获取最佳值来检查。
我们必须要注意的一件事是，一旦我们进入子节点，我们将永远不会回顾父节点。从上面的例子中，我们去 B 从A，因此父[B] = A。因此，我们将不会再回到一个从B。
为了确定基本情况，我们可以注意到，如果从一个节点，我们不能去任何其他新节点，如果我们当前节点中有一个守望者，我们将返回 **1，**如果我们当前没有守望者，则返回 0 节点。
最好有一个树的邻接列表。让列表用 edge 表示。我们将有一个数组 dp [n] [2] ，其中 n 表示存储计算值的节点数，并用 -1 初始化它。我们还将有一个 parent [n] 数组来表示节点之间的父子关系。我们的伪代码看起来像：
Procedure f(u, isGuarded):
if edge[u].size is equal to 0 //node doesn't have any new edge
Return isGuarded
else if dp[u][isGuarded] is not equal to -1 //already calculated
Return dp[u][isGuarded]
end if
sum := 0
for i from i to edge[u].size
v := edge[u][i]
if v is not equal to parent[u] //not a parent
parent[v] := u
if isGuarded equals to 0 //not guarded, must set a watchman
sum := sum + f(v,1)
else //guarded, check both
sum := sum + min(f(v,1), f(v,0)
end if
end if
end for
dp[u][isGuarded] := sum + isGuarded
Return dp[u][isGuarded]
如果我们将节点 A 表示为 root，我们将通过：min(f(A,1), f(A,0)) 调用该函数。这意味着我们还将检查在根节点中设置 watchman 是否最佳。这是我们的 DP 解决方案。使用最大匹配算法或 max-flow 也可以解决此问题。