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

★问题描述：给定一个赋权无向图G=(V,E),每个顶点v∈V都有一个权值w(v)。如果U∈V,且对任意(u,v)∈E有u∈U或v∈U,就称U为图G的一个顶点条覆盖.G的最小权顶点覆盖是指G中所含顶点权之和最小的顶点覆盖。 ★算法设计：对于结定的无向图G,设计一个优先队列式分支限界法,计算G的最小权顶点覆盖。 ★数据输入：由文件input.txt给出输入数据。第1行有2个正整数n和m,表示给定的图G有n个顶点和m条边,顶点编号为1,2,.....,n.第2行有n个正整数表示n个顶点的权.接下来的m行中,每行有2 个正整数u,v,表示图G的一条边(u,v)。 ★结果输出：将计算出的最小权顶点覆盖的顶点权之和以及最优输出到文件output.txt.文件第1行是最小权顶点覆盖顶点权之和;第2行是最优解xi,1≤i≤n,xi=0表示顶点i不在最小权顶点覆盖中。

#include 
#include“MinHeap.h“;
using namespace std;
 

//最小堆结点元素类型是HeapNode
class HeapNode
{
    friend class VertexCover;

public:
    operator int（） const { return cn; }

private:
    int i    //活结点所处的层序号
		cn   //当前权植和
        *x   //当前解
		*c;   //指向活结点在子集树中的结点的指针
};

//解最小权项点覆盖问题的优先队列式分支界限法
class VertexCover
{
    friend int MinCover（int** int[] int）;

private:
    void search（）;
    bool cover（HeapNode E）;
    void AddLiveNode（MinHeap &H HeapNode E int cn int i bool ch）;
    int **a          //图的邻接矩阵
		n            //图的顶点数
		*w           //图中每个顶点的权值
		*bestx      //最优解
		bestn;       //当前最小权值和
};

void VertexCover::search（）
{
    int j;
    MinHeap H（1000）;     //定义最小堆的容量为1000
    HeapNode E;
    E.x = new int[n+1];
    E.c = new int[n+1];
    for（j = 1; j <= n; j++） 
	{
        E.x[j] = E.c[j] = 0;
    }
    int i = 1 cn = 0;      //初始时扩展结点在第一层，权值和为0
    while（1） 
	{
        if（i > n） 
		{//到达叶结点
            if（cover（E）） 
			{  //如果所有结点都覆盖，得到一组顶点覆盖，更新当前最优值和相应的当前最优解
                for（j = 1; j <= n; j++）
                    bestx[j] = E.x[j];
                bestn = cn;
                break;
            }
        } 
		else 
		{//非叶结点
            if（!cover（E）） //结点没有全部覆盖，则添加活结点
                AddLiveNode（H E cn i 1）;    //检查左儿子结点
            AddLiveNode（H E cn i 0）;        //右儿子结点
        }
        if（H.Size（） == 0）   //如果堆容量为0，则跳出循环
            break;

       // 将舍弃结点的存储空间收回
       delete []E.x;
       delete []E.c;

        //取下一扩展结点
        H.DeleteMin（E）;      //堆非空 
        cn = E.cn;
        i = E.i+1;
    }
}

//判定图是否已完全覆盖
bool VertexCover::cover（HeapNode E）
{
    for（int j = 1; j <= n; j++）
        if（ E.x[j] == 0 && E.c[j] == 0 ）
            return false;
    return true;
}

//将活结点加入堆中
void VertexCover::AddLiveNode（MinHeap &H HeapNode E int cn int i bool ch）
{
    int j;
    HeapNode N;   
    N.x = new int[n+1];
    N.c = new int[n+1];
    for（j = 1; j <= n; j++） 
	{
        N.x[j] = E.x[j];
        N.c[j] = E.c[j];
    }
    //检查左儿子结点
    N.x[i]=ch?1:0;
    if（ch） 
	{//可行结点
        N.cn = cn + w[i];
        for（j = 1; j <= n; j++）
            if（a[i][j]）
                N.c[j]++;
    } 
	else
	{
        N.cn = cn;
	}
    N.i = i;
    H.Insert（N）;  //插入到活结点队列
}

//完成最小覆盖计算
int MinCover（int** a int v[] int n）
{
    VertexCover Y;
    Y.w = new int[n+1];      //记录每个结点的权值
    for（int j = 1; j <= n; j++）
        Y.w[j] = v[j];
    Y.a = a;
    Y.n = n;
    Y.bestx = v;
    Y.search（）;
    return Y.bestn;
}

void main（）
{

    int n e u v i j;
    int* p;
    int** a;
    
	cout<<“input.txt:“<    cin >> n >> e;             //输入顶点数和边数
    a = new int*[n+1];
    for（i = 0; i <= n; i++）
        a[i] = new int[n+1];
    for（i = 0; i <= n; i++）
        for（j = 0; j <= n; j++）
            a[i][j] = 0;
    p = new int[

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       3722  2009-12-20 20:45  五、分支限界法\6-2.cpp

     文件       3367  2009-12-23 11:03  五、分支限界法\6-2.dsp

     文件        514  2009-12-23 11:04  五、分支限界法\6-2.dsw

     文件      41984  2009-12-23 11:04  五、分支限界法\6-2.ncb

     文件      48640  2009-12-23 11:04  五、分支限界法\6-2.opt

     文件        733  2009-12-23 11:03  五、分支限界法\6-2.plg

     文件     548928  2009-12-23 11:03  五、分支限界法\Debug\6-2.exe

     文件     257300  2009-12-23 11:03  五、分支限界法\Debug\6-2.obj

     文件    1098752  2009-12-23 11:03  五、分支限界法\Debug\6-2.pdb

     文件     118784  2009-12-23 11:03  五、分支限界法\Debug\vc60.pdb

     文件       1619  2009-12-20 20:02  五、分支限界法\MinHeap.h

     目录          0  2010-07-14 14:07  五、分支限界法\Debug

     目录          0  2009-12-23 11:04  五、分支限界法

----------- ---------  ---------- -----  ----

              2124343                    13