main.cpp

NP问题的顶点覆盖问题的近似算法的Vc++实现

#include  <conio.h>   
#include  <math.h>  

#include  <iostream>  
using namespace std;

#define N 7
 struct adj_list			/*邻接表结点的数据结构*/
{
	int v_num;					/*邻接结点的编号*/
	struct adj_list *next;		/*下一个邻接顶点*/
};
typedef struct adj_list NODE;				
NODE	*V[N];					/*图 的邻接表头结点*/


//中图的矩阵结构转换为图的邻接表结构
void MatrixGraph_To_NodeGraph(int g[N][N],NODE* V[N])
{
	NODE *p ,*q= NULL;
	for(int i = 0; i < N; i++)
	{
		V[i] = new NODE();
		V[i]->v_num = i;
		V[i]->next = NULL;
		p = V[i]->next;
		q = V[i];
		for(int j = 0; j < N; j++)
		{
			
			if(g[i][j])
			{
				NODE* node = new NODE;
				node->v_num = j;
				node->next  = NULL;

				p = V[i]->next;
				while(p)
				{
					q = p;
					p = p->next;
				}

				q->next = node;
			}
		}
	}
}

void DeleteEdge(NODE *V[],int v_index1,int v_index2)
{
	if(!V)
		return;

	NODE* pNode = V[v_index1];

	while(pNode->next)
	{
		if(pNode->next->v_num == v_index2)
		{
			NODE* pNext = pNode->next;					//删除(index1, index2)边
			if(pNext->next)
				pNode->next = pNode->next->next;			//指向后一个指针
			else
				pNode->next = NULL;

			delete pNext;
			pNext = NULL;
			break;
		}
		else
		{
			pNode = pNode->next;
		}
	}

}


//顶点覆盖问题的近似算法
void  VextexCover(NODE *V[],int n, int C[],int &m)
{

	NODE *p,*p1;
	int u,v;
	m = 0;
	for(u = 0; u < n; u++)
	{
		p = V[u]->next;
		if(p != NULL)
		{
			C[m]	= u;
			C[m+1]	= v = p->v_num;
			m += 2;

			while( p != NULL)
			{
				DeleteEdge(V,p->v_num,u);		//删除边(v,u)
				p = p->next;
			}

			V[u]->next = NULL;
			p1 = V[v]->next;

			while( p1 != NULL)
			{
				DeleteEdge(V,p1->v_num,v);		//删除边(v,u)
				p1 = p1->next;
			}

			V[v]->next = NULL;
		}
	}
}

int main(int argc,char* argv[])
{

	*V = new NODE[N];

	int graph[N][N] =
	{
//			  a   b   c   d   e   f   g
/*a*/		{ 0 , 1 , 0 , 0 , 0 , 0 ,0 } ,
/*b*/		{ 1 , 0 , 1 , 0 , 0 , 0 ,0 } ,
/*c*/		{ 0 , 1 , 0 , 1 , 1 , 0 ,0 } ,
/*d*/		{ 0 , 0 , 1 , 0 , 1 , 1 ,1 } ,
/*e*/		{ 0 , 0 , 1 , 1 , 0 , 1 ,0 } ,
/*f*/		{ 0 , 0 , 0 , 1 , 1 , 0 ,0 } ,
/*g*/		{ 0 , 0 , 0 , 1 , 0 , 0 ,0 } ,
	};

	int C[N] = {0};
	int m;

	MatrixGraph_To_NodeGraph(graph,V);
	VextexCover(V,7,C,m);

	printf("approx Vertex Cover Numbers:%d\n",m);

	for(int i =0 ;i< m; i++)
	{
		printf("%d ,",C[i]);
	}

	printf("\n");

	return 0;
}