adj.cpp

数据结构中图的设计。这是图的邻接矩阵的存储结构。

#include"iostream.h"
#include"adj.h"
#include"stdlib.h"
#include"SeqQueue.h"
AdjTWGraph::AdjTWGraph()
{
	for(int i=0;i<MaxVertices;i++)
	{
		Vertices[i].adj=NULL;
	}
	numVertices=0;
	numOfEdges=0;
}
AdjTWGraph::~AdjTWGraph()
{
	for(int i=0;i<numVertices;i++)
	{
		Edge*p=Vertices[i].adj,*q;
		while(p!=NULL)
		{
			q=p->next;
			delete p;
			p=q;
		}
	}
}
VerT AdjTWGraph::GetValue(const int i)
{
	if(i<0||i>numVertices)
	{
		cout<<"参数i出错！"<<endl;
		exit(0);
	}
	return Vertices[i].data;
}
int AdjTWGraph::GetWeight(const int v1,const int v2)
{
	if(v1<0||v1>numVertices||v2<0||v2>numVertices)
	{
		cout<<"参数v1或v2出错！"<<endl;
		exit(0);
	}
	Edge* p=Vertices[v1].adj;
	while(p!=NULL&&p->dest<v2)
		p=p->next;
	if(v2!=p->dest)
	{
		cout<<"edge<v1,v2>don't exist!"<<endl;
		exit(0);
	}
	return p->weight;
}
void AdjTWGraph::InsertVertex(const VerT&vertex)
{
	Vertices[numVertices].data=vertex;
	numVertices++;
}
void AdjTWGraph::InsertEdge(const int v1,const int v2,int weight)
{
	if(v1<0||v1>numVertices||v2<0||v2>numVertices)
	{
		cout<<"参数v1或v2出错！"<<endl;
		exit(0);
	}
	Edge*q=new Edge(v2,weight);
	if(Vertices[v1].adj==NULL)
		Vertices[v1].adj=q;
	else
	{
		Edge* curr=Vertices[v1].adj,*pre=NULL;
		while(curr!=NULL&&curr->dest<v2)
		{
			pre=curr;
			curr=curr->next;
		}
		if(pre==NULL)
		{
			q->next=Vertices[v1].adj;
			Vertices[v1].adj=q;
		}
		else
		{
			q->next=pre->next;
			pre->next=q;
		}
	}
	numOfEdges++;
}
void AdjTWGraph::DeleteVertex(const int v)
{
	Edge*pre,*curr;
	for(int i=0;i<numVertices;i++)
	{
		pre=NULL;
		curr=Vertices[i].adj;
		while(curr!=NULL&&curr->dest<v)
		{
			pre=curr;
			curr=curr->next;
		}
		
		if(pre==NULL&&curr->dest==v)
		{
			Vertices[i].adj=curr->next;
			delete curr;
			numOfEdges--;
		}
		else if(curr!=NULL&&curr->dest==v)
		{
			pre->next=curr->next;
			delete curr;
			numOfEdges--;
		}
	}
	Edge*p=Vertices[v].adj,*q;
	for(i=v;i<numVertices-1;i++)
		Vertices[i]=Vertices[i+1];
	numVertices--;
	while(p!=NULL)
	{
		q=p->next;
		delete p;
		p=q;
		numOfEdges--;
	}
}
void AdjTWGraph::DeleteEdge(const int v1,const int v2)
{
	if(v1<0||v1>numVertices||v2<0||v2>numVertices)
	{
		cout<<"参数v1或v2出错！"<<endl;
		exit(0);
	}
	Edge* curr=Vertices[v1].adj,*pre=NULL;
	while(curr!=NULL&&curr->dest<v2)
	{
		pre=curr;
		curr=curr->next;
	}
	if(pre==NULL&&curr->dest==v2)
	{
		Vertices[v1].adj=curr->next;
		delete curr;
		numOfEdges--;
	}
	else if(pre!=NULL&&curr->dest==v2)
	{
		pre->next=curr->next;
		delete curr;
		numOfEdges--;
	}
	else
	{
		cout<<"edge<v1,v2>don't exist!"<<endl;
		exit(0);
	}
}
int AdjTWGraph::GetFirstNeighbor(const int v)
{
	if(v<0||v>numVertices)
	{
		cout<<"参数v出错！"<<endl;
		exit(0);
	}
	Edge* p=Vertices[v].adj;
	if(p!=NULL)
		return p->dest;
	else return -1;
}
int AdjTWGraph::GetNextNeighbor(const int v1,const int v2)
{
	if(v1<0||v1>numVertices||v2<0||v2>numVertices)
	{
		cout<<"参数v1或v2出错！"<<endl;
		exit(0);
	}
	Edge*p=Vertices[v1].adj;
	while(p!=NULL)
	{
		if(p->next!=NULL&&p->dest==v2)
			return p->next->dest;
		else p=p->next;
	}
	return -1;
}
void AdjTWGraph::DepthFirstSearch(const int v,int visited[],void visit(VerT item))
{
	visit(GetValue(v));
	visited[v]=1;
	int w=GetFirstNeighbor(v);
	while(w!=-1)
	{
		if(!visited[w])
			DepthFirstSearch(w,visited,visit);
		w=GetNextNeighbor(v,w);
	}
}
void AdjTWGraph::DepthFirstSearch(void visit(VerT item))
{
	int *visited=new int[NumOfVertices()];
	for(int i=0;i<NumOfVertices();i++)
		visited[i]=0;
	for(i=0;i<NumOfVertices();i++)
		if(!visited[i])
			DepthFirstSearch(i,visited,visit);
		delete []visited;
}
void AdjTWGraph::BroadFirstSearch(const int v,int visited[],void visit(VerT item))
{
	SeqQueue myqueue;
	int u,w;
	visit(GetValue(v));
	visited[v]=1;
	myqueue.QInsert(v);
	while(!myqueue.QEmpty())
	{
		u=myqueue.QDelete();
		w=GetFirstNeighbor(u);
		while(w!=-1)
		{
			if(!visited[w])
			{
				visit(GetValue(w));
				myqueue.QInsert(w);
				visited[w]=1;
			}
			w=GetNextNeighbor(u,w);
		}
	}
}
void AdjTWGraph::BroadFirstSearch(void visit(VerT item))
{
	int* visited=new int[NumOfVertices()];
	for(int i=0;i<NumOfVertices();i++)
		visited[i]=0;
	for(i=0;i<NumOfVertices();i++)
		if(!visited[i])
			BroadFirstSearch(i,visited,visit);
	delete []visited;
}