graph.h

图的常用算法

#ifndef GRAPH_CLASS
#define GRAPH_CLASS

#include <iostream.h>
#include <iomanip.h>
#include <fstream.h>
#include <limits.h>

#include "Queue.h"
#include "SeqList.h"

const int MaxGraphSize=25;

const int INFINITY=INT_MAX;

template <class T>
class Graph
{
	private:
		SeqList<T> vertexList;
		int edge[MaxGraphSize][MaxGraphSize];
		int vertexNumber;

		int GetVertexPos(const T &vertex);
		int FindVertex(SeqList<T> &l,const T & vertex);

	public:
		Graph(void);

		int GraphEmpty(void) const;
		int GraphFull(void) const;

		int NumberOfVertices(void) const;
		int GetWeight(const T &vertex1,const T &vertex2);
		SeqList<T> GetNeighbors(int v);

		void InsertVertex(const T &vertex);
		void InsertEdge(const T &vertex1,const T &vertex2,int Weight);
		void DeleteVertex(const T &vertex);
		void DeleteEdge(const T &vertex1,const T &vertex2);

		int GetFirstNeighbor(int v);
		int GetNextNeighbor(int v1,int v2);

		void ReadGraph(char * filename);
		void PrintEdge()const;

		void DFS(int v);
		void DFS(int v,int visited[]);
		void BFS(int v);

		void ShortestPath(int v,int path[],int dist[],int S[]);
		void OutputShortestPath(int start,Graph<T> & G);
};

template <class T>
Graph<T>::Graph(void):vertexList(MaxGraphSize)
{
	for(int i=0;i<MaxGraphSize;i++)
		for(int j=0;j<MaxGraphSize;j++)
			edge[i][j]=INFINITY;
		vertexNumber=0;
}

template <class T>
int Graph<T>::NumberOfVertices(void) const
{
	return vertexNumber;
}

template <class T>
int Graph<T>::GraphEmpty(void) const
{
	return vertexNumber==0;
}

template <class T>
int Graph<T>::GraphFull(void) const
{
	return vertexNumber==MaxGraphSize;
}

template <class T>
void Graph<T>::ReadGraph(char *filename)
{
	int i,nvertices,nedges;
	T S1,S2;
	int weight;
	ifstream f;
	f.open(filename);
	if(!f)
	{
		cerr<<"Cannot open"<<filename<<endl;
		exit(1);
	}
	f>>nvertices;
	for(i=0;i<nvertices;i++)
	{
		f>>S1;
		InsertVertex(S1);
	}
	f>>nedges;
	for(i=0;i<nedges;i++)
	{
		f>>S1;
		f>>S2;
		f>>weight;
		InsertEdge(S1,S2,weight);
	}

	for(i=0;i<nvertices;i++)
	{
		InsertEdge(i,i,0);
	}
	f.close();
}

template <class T>
void Graph<T>::InsertVertex(const T & vertex)
{
	if(vertexNumber+1>MaxGraphSize)
	{
		cerr<<"Graph::InsertVertex:Graph full!"<<endl;
		exit(1);
	}
	vertexList.Insert(vertex);
	vertexNumber++;
}

template <class T>
void Graph<T>::InsertEdge(const T & vertex1,
						  const T & vertex2,int weight)
{
	int pos1=GetVertexPos(vertex1);
	int pos2=GetVertexPos(vertex2);
	if(pos1==-1||pos2==-1)
	{
		cerr<<"Graph::InsertEdge:vertex not in the graph."
			<<endl;
		return;
	}
	edge[pos1][pos2]=weight;
}

template <class T>
void Graph<T>::PrintEdge()const
{
	for(int i=0;i<vertexNumber;i++)
	{
		for(int j=0;j<vertexNumber;j++)
		{
			if(edge[i][j]==INFINITY)
				cout<<setw(4)<<"∞";
			else
				cout<<setw(4)<<edge[i][j];
		}
	cout<<endl;
	}
}

template <class T>
int Graph<T>::GetVertexPos(const T & vertex)
{
	int pos=vertexList.Find(vertex);
	if(pos==-1)
	{
		cerr<<"Graph::GetVertexPos:vertex not in the graph"
			<<endl;
		return -1;
	}
	return pos;
}

template <class T>
int Graph<T>::GetWeight(const T & vertex1,const T & vertex2)
{
	int pos1=GetVertexPos(vertex1);
	int pos2=GetVertexPos(vertex2);
	if(pos1==-1||pos2==-1)
	{
		cerr<<"Graph::GetWeught:vertex not in the graph."
			<<endl;
		return -1;
	}
	return edge[pos1][pos2];
}

template <class T>
SeqList<T> Graph<T>::GetNeighbors(int v)
{
	SeqList<T> L;
	int j=0;
	if(v<0||v>=vertexNumber)
	{
		cerr<<"Graph::GetNeighbor:vertex not int the graph"
			<<endl;
		return L;
	}
	for(int i=0;i<vertexNumber;i++)
	{
		if(edge[v][i]>0&&edge[v][i]<INFINITY)
		{
			L.Insert(vertexList[i]);
		}
	}
	return L;
}

template <class T>
int Graph<T>::GetFirstNeighbor(int v)
{
	int n=vertexList.Length();
	if(v!=-1&&v>=0&&v<n)
	{
		for(int col=0;col<n;col++)
		{
			if(edge[v][col]>0&&edge[v][col]<INFINITY)
				return col;
		}
	}
	return -1;
}

template <class T>
int Graph<T>::GetNextNeighbor(int v1,int v2)
{
	int n=vertexList.Length();
	if(v1!=-1&&v1>=0&&v1<n&&v2!=-1&&v2>=0&&v2<n)
	{
		for(int col=v2+1;col<=n;col++)
		{
			if (edge[v1][col]>0&&edge[v1][col]<INFINITY)
			return col;
		}
	}
	return -1;
}

template <class T>
void Graph<T>::DeleteVertex(const T & vertex)
{
	int pos=GetVertexPos(vertex);
	int row,col;
	if(pos==-1)
	{
		cerr<<"Graph::DeleteVertex:vertex not in the graph."
			<<endl;
		return;
	}
	vertexList.Delete(vertex);
	vertexNumber--;
	for(row=0;row<pos;row++)
	{
		for(col=pos+1;col<vertexNumber;col++)
			edge[row][col-1]=edge[row][col];
	}
	for(row=pos+1;row<vertexNumber;row++)
	{
		for(col=pos+1;col<vertexNumber;col++)
			edge[row-1][col-1]=edge[row][col];
	}
	for(row=pos+1;row<vertexNumber;row++)
	{
		for(col=0;col<pos;col++)
			edge[row-1][col]=edge[row][col];
	}
}

template <class T>
void Graph<T>::DeleteEdge(const T & vertex1,const T & vertex2)
{
	int pos1=GetVertexPos(vertex1);
	int pos2=GetVertexPos(vertex2);
	if(pos==-1||pos2==-1)
	{
		cerr<<"Graph::DeleteEdge:vertex not in the graph"
			<<endl;
		return;
	}
	edge[pos1][pos2]=0;
}

template <class T>
void Graph<T>::DFS(int v)
{
	int n=vertexList.Length()+1;
	int *visited=new int[n];
	assert(visited!=NULL);
	for(int i=0;i<n;i++)
		visited[i]=0;
	DFS(v,visited);
	delete []visited;
}

template <class T>
void Graph<T>::DFS(int v,int visited[])
{
	cout<<vertexList[v]<<" ";
	visited[v]=1;
	int w=GetFirstNeighbor(v);
	while(w!=-1)
	{
		if(visited[w]==0)
			DFS(w,visited);
		w=GetNextNeighbor(v,w);
	}
}

template <class T>
void Graph<T>::BFS(int v)
{
	int n=vertexList.Length()+1;
	int *visited=new int[n];
	assert(visited!=NULL);
	for(int i=0;i<n;i++)
		visited[i]=0;
	cout<<vertexList[v]<<" ";
	visited[v]=1;
	Queue<int> q;
	q.EnQueue(v);
	while(q.DeQueue(v))
	{
		int w=GetFirstNeighbor(v);
		while(w!=-1)
		{
			if(visited[w]==0)
			{
				cout<<vertexList[w]<<" ";
				visited[w]=1;
				q.EnQueue(w);
			}
			w=GetNextNeighbor(v,w);
		}
	}
	delete []visited;
}

template <class T>
void Graph<T>::ShortestPath(int v,int path[],int dist[],int S[])
{
	for(int i=0;i<vertexNumber;i++)
	{
		dist[i]=edge[v][i];
		S[i]=0;
		if(i!=v&&dist[i]<INFINITY)
			path[i]=v;
		else 
			path[i]=-1;
	}
	S[v]=1;dist[v]=0;
	for(i=0;i<vertexNumber-1;i++)
	{
		int min=INFINITY;int u=v;
		for(int j=0;j<vertexNumber;j++)
			if(!S[j]&&dist[j]<min)
			{
				u=j;
				min=dist[j];
			}
			S[u]=1;
			for(int w=0;w<vertexNumber;w++)
				if(!S[w]&&edge[u][w]<INFINITY&&dist[u]+edge[u][w]<dist[w])
				{
					dist[w]=dist[u]+edge[u][w];
					path[w]=u;
				}
	}
}

template <class T>
void Graph<T>::OutputShortestPath(int start,Graph<T> & G)
{
	cout<<"The shortest path degree:"<<endl;
	int path[MaxGraphSize];
	int dist[MaxGraphSize];
	int S[MaxGraphSize];
	G.ShortestPath(start,path,dist,S);
	cout<<"The shortest path:"<<endl;
	int v;
	cout<<"Weight   path"<<endl;
	for(int i=0;i<vertexNumber;i++)
	{
		cout<<setw(5)<<dist[i];
		cout<<setw(5)<<i;
		v=path[i];
		while(v!=-1)
		{
			cout<<"    "<<v;
			v=path[v];
		}
		cout<<endl;
	}
}

#endif