graph.h

关于图的一个程序

// 我真诚地保证：
//   
// 我自己独立地完成了整个程序从分析、设计到编码的所有工作。
// 如果在上述过程中，我遇到了什么困难而求教于人，那么，我将在程序实习报告中
// 详细地列举我所遇到的问题，以及别人给我的提示。
//
// 我的程序里中凡是引用到其他程序或文档之处，
// 例如教材、课堂笔记、网上的源代码以及其他参考书上的代码段,
// 我都已经在程序的注释里很清楚地注明了引用的出处。
//
// 我从未没抄袭过别人的程序，也没有盗用别人的程序，
// 不管是修改式的抄袭还是原封不动的抄袭。
//
// 我编写这个程序，从来没有想过要去破坏或妨碍其他计算机系统的正常运转。
//   



#include "queue"
using namespace std;

template <int max_size>
class CGraph
{
protected:
	int		size;
	CEdge	*peg[max_size];
public:
	CGraph();
	~CGraph(){};
	bool Insert();				//添加一个顶点
	bool Insert(int num);		//添加多个顶点
	bool Link(int a, int b);	//在两点之间加一条边
	void dfs(int n,void(*visit)(int index));				//深度遍历
	bool bfs(int n,void(*visit)(int index));				//广度遍历
	bool spath(int v1, int v2, int k, void(*visit)(int index));	//在两点之间查找定长路经
	int slp(int v1, int v2, void(*visit)(int index));		//在两点之间查找最长路经
	void clear();				//清空
	bool exist(int a, int b);	//判断一条边是否存在
protected:
	void dfs(int n,int visited[],void(*visit)(int index));	//深度遍历
	bool spath(int v1, int v2, int k, int p[], void(*visit)(int index));	//在两点之间查找定长路经
};

template <int max_size>
CGraph<max_size>::CGraph()
//	功能:	
{
	int	i;
	size=0;
	for(i=0;i<max_size;i++)
		peg[i]=NULL;
}

template <int max_size>
bool CGraph<max_size>::Insert()
//	功能:	添加一个顶点
//	返回值:	添加是否成功
{
	if(size>=max_size)	return false;
	size++;
	return true;
}

template <int max_size>
bool CGraph<max_size>::Insert(int num)
//	功能:	添加多个顶点
//	返回值:	添加是否成功
//	参数:	添加的顶点个数
{
	if( size>(max_size-num) )	return false;
	size+=num;
	return true;
}

template <int max_size>
bool CGraph<max_size>::Link(int a, int b)
//	功能:	在两点之间添加一条边
//	返回值:	添加是否成功
//	参数:	边的两个顶点
{
	CEdge	*temp;
	if(exist(a, b))	return false;
	if( a>=size || b>=size )	return false;
	temp   = peg[a];
	peg[a] = new CEdge(b, temp);	//从a到b
	temp   = peg[b];
	peg[b] = new CEdge(a, temp);	//从b到a
	return true;
}

template <int max_size>
void CGraph<max_size>::dfs(int n,void(*visit)(int index))
//	功能:	深度遍历
//	参数:
//		n:		遍历的起点
//		visit:	访问函数
{
	int i;
	int	visited[max_size];			//访问标记
	for(i=0;i<max_size;i++)
		visited[i]=0;
	dfs(n,visited,visit);
	for(i=0;i<size;i++)
		if(!visited[i])
		{
			dfs(i,visited,visit);
		}
	visit(-1);						//换行
}

template <int max_size>
void CGraph<max_size>::dfs(int n,int visited[],void(*visit)(int index))
//	功能:	深度遍历
//	参数:
//		n:		遍历的起点
//		visited:遍历过的点
//		visit:	访问函数
{
	CEdge	*e;
	visited[n]=1;
	visit(n);
	e=peg[n];
	while(e)
	{
		if(!visited[e->vertex])
			dfs(e->vertex,visited,visit);	//递归
		e=e->next;					//下一条边
	}
}

template <int max_size>
bool CGraph<max_size>::bfs(int n,void(*visit)(int index))
//	功能:	广度遍历
//	参数:
//		n:		遍历的起点
//		visit:	访问函数
{
	int			i;
	int			visited[max_size];			//访问标记
	queue<int>	q;
	CEdge		*e;
	for(i=0;i<max_size;i++)
		visited[i]=0;
	if(n>=size)	return false;
	q.push(n);
	while(!q.empty())						//队列不为空
	{
		int t = q.front();
		e=peg[t];
		if(!visited[t])
		{
			visited[t]=1;					//置访问标记
			visit(t);						//输出
			while(e)
			{								//将与该点相连的所有未访问过的点加入队列中
				if(!visited[e->vertex])
					q.push(e->vertex);
				e=e->next;					//下一条边
			}
		}
		q.pop();							//弹出访问过的点
	}
	visit(-1);
	return true;
}

template <int max_size>
bool CGraph<max_size>::spath(int v1, int v2, int k, void(*visit)(int index))
//	功能:	在两点之间查找定长路径
//	返回值:	是否找到要求的路径
//	参数:
//		v1:		起始点
//		v2:		终止点
//		k:		路径长度
//		visit:	访问函数
{
	int *p = new int[k];
	int	i;
	for(i=0;i<k;i++)
		p[i]=-1;
	if(k>size)	return false;
	p[0] = v1;
	return spath(v1, v2, k, p, visit);
}

template <int max_size>
bool CGraph<max_size>::spath(int v1, int v2, int k, int p[], void(*visit)(int index))
//	功能:	在两点之间查找定长路径
//	返回值:	是否找到要求的路径
//	参数:
//		v1:		起始点
//		v2:		终止点
//		k:		路径长度
//		p:		走过的路径
//		visit:	访问函数
{
	int		i;	
	CEdge	*e;
	e = peg[v1];
	bool	f=false;
	while(e)
	{
		bool	flag=true;
		for(i=0;i<k;i++)
		{							//检查是否访问过该点
			if( p[i]==-1 )	break;	//检查终止
			if( e->vertex==p[i] )	
			{						//该点已被访问过
				flag=false;
				break;
			}
		}
		if( i==k )	flag=false;
		if( e->vertex==v2 )
		{
			if( i==k )
			{						//找到路径
				for(i=0;i<k;i++)
					visit(p[i]);
				visit(v2);
				visit(-1);
				return true;
			}
			else
				flag=false;			//路径过短
		}
		if(flag)
		{							//该点未被访问过
			p[i] = e->vertex;		//将该点计入路径
			if(spath(e->vertex, v2, k, p, visit))
				f=true;
			p[i] = -1;
		}
		e=e->next;					//下一条边
	}
	return f;
}
template <int max_size>
int CGraph<max_size>::slp(int v1, int v2, void(*visit)(int index))
//	功能:	在两点之间查找最长路径
//	返回值:	最长路经的长度
//	参数:
//		v1:		起始点
//		v2:		终止点
//		visit:	访问函数
{
	int		i;
	for( i=size-1; i>0; i--)
	{
		if(spath(v1, v2, i, visit))	
		{							//该长度存在路径
			return i;
		}
	}
	return 0;
}

template <int max_size>
void CGraph<max_size>::clear()
//	功能:	清空图
{
	int	i;
	size=0;
	for(i=0;i<max_size;i++)
		peg[i]=NULL;
}

template <int max_size>
bool CGraph<max_size>::exist(int a, int b)
//	功能:	判断一条边是否存在
//	返回值:	该边是否存在
//	参数:	该边的两个顶点
{
	CEdge	*e;
	e = peg[a];
	while(e)
	{
		if( e->vertex==b )	return true;	//是要找的边
		e = e->next;						//下一条边
	}
	return false;
}