adjmwgraph.h

主要是图的建立

#include<iostream.h>
#include<stdlib.h>
#include "SeqList.h"
typedef  char VerT;
//const int MaxVertices=200;        //设定顶点数最大值
const int MaxWeight=10000;       //设定权值的无限大
class AdjMWGraph            //AdjMWGraph<T>类的定义
{
private:
      SeqList Vertices;
	  int Edge[MaxVertices][MaxVertices];
	   int numOfEdges;
public:
      AdjMWGraph (const int sz=MaxVertices);
	  int GraphEmpty()const {return Vertices.ListEmpty();}
	  int NumOfVertices(void) {return Vertices.ListSize();}
	  int NumOfEdges(void) {return numOfEdges;}
	  VerT GetValue(const int i);
	  int GetWeight(const int v1,const int v2);
	  void InsertVertex(const VerT & vertex);
	  void InsertEdge(const int v1,const int v2,int weight);
	  int GetFirstNeighbor(const int v);
      int GetNextNeighbor(const int v1,const int v2);

	  void DeleteVertex(const v);
	  void DeleteEdge(const int v1,const int v2);

	  void BroadFirstSearch(const int v,int visited[],void visit(VerT item));
	  void BroadFirstSearch(void visit(VerT item));
	  void DepthFirstSearch(const int v, int visited[],void visit(VerT item));
	  void DepthFirstSearch(void visit(VerT item));
};
AdjMWGraph::AdjMWGraph(const int sz)
{
	for(int i=0;i<sz;i++)
		for(int j=0;j<sz;j++)
		{
			if(i==j)Edge[i][j]=0;
				else Edge[i][j]=MaxWeight;
		}
		numOfEdges=0;
}
VerT AdjMWGraph::GetValue(const int i)
{
	if(i<0||i>Vertices.ListSize())
	{
		cout<<"参数越界出错!"<<endl;
		exit(0);
	}
	return Vertices.GetData(i);
}
int AdjMWGraph::GetWeight(const int v1,const int v2)
{
	if(v1<0||v1>Vertices.ListSize()||v2<0||v2>Vertices.ListSize())
	{
		cout<<"参数越界出错!"<<endl;
		exit(0);
	}
	return Edge[v1][v2];
}

void AdjMWGraph::InsertVertex(const VerT&vertex)
{
	Vertices.Insert(vertex,Vertices.ListSize());
}

void AdjMWGraph::InsertEdge(const int v1,const int v2,int weight)
{
	if(v1<0||v1>Vertices.ListSize()||v2<0||v2>Vertices.ListSize())
	{
		cout<<"参数越界出错!"<<endl;
        exit(0);
	}
	Edge[v1][v2]=weight;
	numOfEdges++;
}


void AdjMWGraph::DeleteEdge(const int v1,const int v2)
{
	if(v1<0 || v1>Vertices.ListSize() || v2<0 ||v2>Vertices.ListSize())
	{
		cerr<<"参数 v1或v2出错!"<<endl;
		exit(1);
	}
	Edge[v1][v2]=MaxWeight;
	numOfEdges--;
}



void AdjMWGraph::DeleteVertex(const v)
{
   for(int i=0;i<Vertices.ListSize();i++)
	 for(int j=0;j<Vertices.ListSize();j++)
		 if((i==v || j==v) && Edge[i][j]>0 && Edge[i][j]<MaxWeight)
		 {
			 Edge[i][j]=MaxWeight;
			 numOfEdges--;
		 }
	Vertices.Delete(v);
}

void AdjMWGraph::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 AdjMWGraph::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;

}

/****书上的graphlib.h****/

struct RowColWeight
{
	int row;
	int col;
	int weight;
};
void Printchar(char item)
{
	cout<<item<<" ";
}

void CreatGraph(AdjMWGraph &G,DataType V[],int n,RowColWeight E[],int e)
{   

	for(int i=0;i<n;i++) G.InsertVertex(V[i]);
	for(int k=0;k<e;k++)
		G.InsertEdge(E[k].row,E[k].col,E[k].weight);
}


int AdjMWGraph::GetFirstNeighbor(const int v)
{
	if(v<0||v>Vertices.ListSize())
	{
		cout<<"参数越界出错!"<<endl;
	    exit(0);
	}
    for(int col=0;col<=Vertices.ListSize();col++)
		if(Edge[v][col]>0&&Edge[v][col]<MaxWeight) return col;
    return -1;
}


int AdjMWGraph::GetNextNeighbor(const int v1,const int v2)
{
	if(v1<0||v1>Vertices.ListSize()||v2<0||v2>Vertices.ListSize())
	{
		cout<<"参数v1或v2越界出错!"<<endl;
	    exit(0);
	}
	for(int col=v2+1;col<=Vertices.ListSize();col++)
		if(Edge[v1][col]>0&&Edge[v1][col]<MaxWeight) return col;
    return -1;
}

/*void AdjMWGraph::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 AdjMWGraph::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;
}*/