分支限界法之最小权顶点覆盖问题

我们先简明介绍一下题目，我们仍然需要将所有点分成U、V两个集合。什么叫做顶点覆盖呢？即为V 集合中的每个点，至少与一个U集合中的点直接相连。如图所示（红色点表示U集合中的点）： 我们可以看到V集合中的顶点2、5、6，都与至少一个U集合中的顶点直接相连。反而如果按照下图分配则不满足条件： 图中V集合的顶点2、5并没有U集合中的点与其直接相连，所以不是一种顶点覆盖。

那我们应该如何判断图是否被覆盖了呢？可以开辟一个数组c，如果c[j]==0，则表示U集合中没有任何一个顶点与其直接相连。 优先级 说完如何判断是否覆盖之后，我们来确定一下优先级。由于所有顶点都是带权的，我们的目的也是找到最小权覆盖，所以我们可以直接用权重作为优先级建立一个最小堆，从而实现优先队列。 界限函数 我们找的是最小点权，无法使用界限函数来对右孩子进行约束，因为如果当前结点不加入U集合中(即走右孩子路径)，一定点权和更小，但是不一定会覆盖，所以不经过判断，我们也要将右孩子加入到队列中。 将活结点加入队列中 将活结点加入队列时，要对点的优先级、结果向量以及cover数组进行更新。