最小顶点覆盖问题

最小顶点覆盖问题

已知 G 为一个无向图。给定一个 G 的一个顶点子集 U，当且仅当G 中的每一条边必有一个顶点属于 U 或者两个顶点都属于 U 时，称 U 是 G 的一个顶点覆盖（vertex cover），U 中顶点的数量是覆盖的大小(size)。设计一个求解最小顶点覆盖的分支限界算法，并分析算法的时间复杂度。（描述算法策略并写出代码）

算法策略：

假设G=<V,E>,V为G的顶点集合，E为G的边集合

算法策略：可以采用贪心加减枝的策略。令一个全局变量bestw为当前能找到的最小覆盖的顶点数（初始为G中顶点数，表示未找到）。令树中的结点为一个状态，这个状态的信息包括了已选择了的顶点集合A和它的数量num_of_A。还未覆盖的边集合C以及边数num_of_C，接下来可以选择的图中的顶点集合X，以及这些顶点能与C建立联系的边数优先队列Q（意思就是这个顶点能与C中x个边联系，则这个顶点在队列的值就是x；然后优先队列意思就是那个顶点能与C建立联系的边数大，哪个就在队列的前面）。

从一个树种结点扩展左右子树时，我们这样定义向左扩展意为从Q中弹出一个顶点（根据先前优先队列定义，这个顶点能与C中建立最多的联系），然后这个顶点加入到A中，num_of_A++。并且C也要减去与这个顶点有联系的结点，num_of_C也做出相应的调整。X的变化是减去弹出的这个顶点。Q的变化即为弹出。然后将这些信息构成的状态结点添加到左子树上，并且这个结点入队（入的队后面说）。然后检查一下num_of_C，若为0说明找到了一个覆盖集合，然后这个结点不入队.若num_of_A小于bestw，则更新bestw，并且另一个选择序列B=A，以便输出。

向右扩展也一样，从Q中弹出一个顶点，但是这个顶点不加入A中，那么A不变，C不变，X要减去弹出的这个顶点。Q的变化即为弹出。而且向右不可能找到覆盖集合。然后将这些信息构成的状态结点添加到右子树上，并且这个结点入队。

那么再定义一下扩展顺序，所有树中的结点都根据num_of_C来排列，优先扩展num_of_C最小的。也就是维护一个num_of_C的优先队列。若队列空了那么bestw则为对应的顶点数

再来确定一下限界策略，向左扩展前，检查一下num_of_A，若num_of_A+1后大于bestw，则停止扩展左子树，即不入队。去扩展右子树。向右扩展不做这样的检查。

而向左向右扩展都有不能完全覆盖的危险。检查Q,若Q中前bestw的结点的和小于num_of_C或者X的数目小于bestw，则停止扩展。

算法顺序是这样的：

1.初始化根节点加入优先队列中

2.若队列不为空，则从优先队列中取出一个结点进入步骤3，否则退出，输出B

3.扩展这个结点的左右子树，分别对左右子树运用限界，不满足限界则不加入优先队列。满足则加入优先队列

然后这个树的根节点就是未选择任何一个顶点的状态。那么C=V,Q=V。然后再进行上述循环即可

#include <iostream>
#include<queue>
using namespace std;#define num_of_point 7int bestw = num_of_point;
int B[10];
int G[10][10];//编号从0开始,无向图说明对称,对角线规定为0
typedef struct pot {int num;//顶点编号int a;//可与C建立联系数pot(int x = 0, int y = 0) {num = x;a = y;}}pot;//int num_of_point;bool operator<(pot a, pot b)
{return a.a < b.a;//最大值优先
}typedef struct node {int matrix[num_of_point][num_of_point];//表示未建立联系边的矩阵int num_of_c;//未建立联系的边数int A[num_of_point];//已选顶点的编号,-1表示未选priority_queue<pot> q;//可选顶点的集合}node;//树中结点结构体void init(node* child, node* parent) {//child->matrix = new int* [num_of_point];//child->A = new int[num_of_point];//for (int i = 0; i < num_of_point; i++)//	child->matrix[i] = new int[num_of_point];for (int i = 0; i < num_of_point; i++) {child->A[i] = parent->A[i];}for (int i = 0; i < num_of_point; i++) {for (int j = 0; j < num_of_point; j++) {child->matrix[i][j] = parent->matrix[i][j];}}child->q = parent->q;child->num_of_c = parent->num_of_c;
}//拷贝构造函数bool operator<(node a, node b)
{return a.num_of_c > b.num_of_c;//最小值优先
}priority_queue<node> Qoftree;//他就是树void add_left(node* p) {int k = 0;pot x = p-&p();p->q.pop();//弹出一个顶点for (k = 0; p->A[k] != -1; k++);//找到第一个是-1，表示第一个未做选择的位置以便于插入p->A[k++] = x.num;//k即为numofAif (k > bestw)return;//限界策略for (int i = 0; i < num_of_point; i++){p->matrix[i][x.num] = 0;p->matrix[x.num][i] = 0;}//更新一下啊qpot y[num_of_point];int kk = 0;while (!p-&pty()){y[kk] = p-&p();p->q.pop();y[kk].a = 0;for (int j = 0; j < num_of_point; j++){if (p->matrix[y[kk].num][j] == 1)y[kk].a++;}kk++;}for (int i = 0; i < kk; i++){p->q.push(y[i]);}p->num_of_c = 0;for (int i = 1; i < num_of_point; i++) {for (int j = 0; j < i; j++) {if (p->matrix[i][j] == 1)p->num_of_c++;}}if (p->num_of_c == 0 && k < bestw) {bestw = k;for (int i = 0; i < k; i++)B[i] = p->A[i];}if (p->num_of_c != 0 && !(p-&pty())) {Qoftree.push(*p);//入队}
}void add_right(node* p) {p->q.pop();//弹出之后检查，是否还能形成覆盖int i = 0, surplus_choice = 0, sum = 0;//i即为numofA,surplus_choice为前bestw-numofA(表示最多还可选的顶点再选这么多个就到bestw了),sum为它们的和pot x[num_of_point];for (i = 0; p->A[i] != -1; i++);surplus_choice = bestw - i;int k = 0;if (p->q.size() >= surplus_choice)//p->q.size()表示还可以选择的顶点数目{for (k = 0; k < surplus_choice; k++){x[k] = p-&p();sum += x[k].a;p->q.pop();}}else {while (!p-&pty()) {x[k] = p-&p();sum += x[k].a;p->q.pop();k++;}}if (sum < p->num_of_c)return;for (int j = 0; j < k; j++) {p->q.push(x[j]);}Qoftree.push(*p);}int main()
{int** G;int num_of_vetic;//顶点数目cin >> num_of_vetic;G = new int* [num_of_point];for (int i = 0; i < num_of_point; i++)G[i] = new int[num_of_point];for (int i = 0; i < num_of_point; i++){for (int j = 0; j < num_of_point; j++){G[i][j] = 0;}}for (int i = 0; i < num_of_vetic; i++){int k, j;cin >> k >> j;G[k][j] = G[j][k] = 1;}node parent_of_all;//parent_of_all.A = new int[num_of_point];//parent_of_all.matrix = new int* [num_of_point];//for (int i = 0; i < num_of_point; i++)//	parent_of_all.matrix[i] = new int[num_of_point];for (int i = 0; i < num_of_point; i++){parent_of_all.A[i] = -1;}for (int i = 0; i < num_of_point; i++){for (int j = 0; j < num_of_point; j++){parent_of_all.matrix[i][j] = G[i][j];}}parent_of_all.num_of_c = num_of_vetic;for (int i = 0; i < num_of_point; i++){pot x(i, 0);//i为编号for (int j = 0; j < num_of_point; j++){if (G[i][j] == 1)x.a++;}parent_of_all.q.push(x);}Qoftree.push(parent_of_all);while (!pty()) {node left, right;node x = p();Qoftree.pop();init(&left, &x);init(&right, &x);add_left(&left);add_right(&right);}cout << bestw;for (int i = 0; i < bestw; i++)cout << "  " << B[i];}