graph.cpp

经典的着色问题

// Graph.cpp: implementation of the Graph class.
//
//////////////////////////////////////////////////////////////////////
#include "Graph.h"
#include"queue.h"
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
Graph::Graph()
{
	vet=NULL;
	dot=NULL;
}
Graph::~Graph()
{
	if(dot!=NULL)delete [] dot;
	if(vet!=NULL)delete [] vet;
}
bool Graph::isedge(edge w)
{
	return w!=NULL;
}
edge Graph::next(edge w)
{
	int stop=(v1(w)+1)*vetnum;
	for(int pos=(w-vet)+1;pos<stop;pos++)
		if(vet[pos]==1)return &vet[pos];
		return NULL; 
}
int Graph::v1(edge w)
{
	return (w-vet)/vetnum;
}
int Graph::v2(edge w)
{
	return (w-vet)%vetnum;
}
edge Graph::first(int v)
{
	int stop=(v+1)*vetnum;
	for(int pos=v*vetnum;pos<stop;pos++)
		if(vet[pos]==1)return &vet[pos];
		return NULL;
}
void Graph::makegraph(ifstream &in,int m)
{
	vetnum=m;
	vet=new int[m*m];
	dot=new struct node[m];
	for(int i=0;i<m;i++){
		dot[i].visit=dot[i].color=0;
	}
	for(int j=0;j<m*m;j++){
	   in>>vet[j];
	   if(j%(m+1)==0)vet[j]=0;
	   if(vet[j]==1)edgnum++;
	   }
	edgnum=edgnum/2;
}
int Graph::travel(int v)
{
	queue q=queue(vetnum);
	q.inqueue(v);
	dot[v].color=1;
	int *m=new int[vetnum+1];
	for(int j=0;j<=vetnum;j++)
		m[j]=0;
	while(!q.isempty()){
		int u=q.del();
		dot[u].visit=2;
		for(edge w=first(u);isedge(w);w=next(w)){
			int s=v2(w);
			if(dot[s].visit==0){q.inqueue(s),dot[s].visit=1;}
			else if(dot[s].visit==2)m[dot[s].color]=1;
		}
			for(int i=1;i<=vetnum;i++)
				if(m[i]==0){dot[u].color=i;break;}
				for(int j=1;j<=vetnum;j++)
					m[j]=0;
	}
	int ss=0;
	for(int a=1;a<=vetnum;a++)
		if(ss<dot[a].color)ss=dot[a].color;
		return ss;
}