图的搜索.cpp

图的深度优先搜索和广度优先搜索

#include<iostream>
using namespace std;
struct vertex									//节点
{
	bool _new;									//被访问过了?
	unsigned adj_ver_numb;						//邻接节点数目
	unsigned * adj;								//邻接节点索引数组
	int _data;									//节点内容
	unsigned _pos;								//自己的索引
};
template<class T, const int size> class _queue	//循环队列模板类
{
public:
	_queue(void){ head = tail = queue; };
	T _deQueue(void)							//对头出列
	{
		if( head < queue + size - 1 )
			return *head++;
		else									//队列头已经到了数组尾，开始循环
		{
			T temp = *head;						
			head = queue;
			return temp;
		}
	};					
	void _enQueue( const T & data )
	{ 
		if( tail < queue + size - 1 )
			*tail++ = data;						//添加元素到队尾
		else									//队列尾已经到了数组尾，开始循环
		{
			*tail = data;
			tail = queue;
		}
	};	
	bool _empty(void){ return head == tail; };	//队列已经空了吗？
	~_queue(void){};
private:
	T queue[size];
	T * head, * tail;
};
class _graph
{
public:
	_graph(void);								//建立邻接表
	void _initial(void);						//初始化，使所有的节点都处于未被访问的状态
	void _DFS(void);							//深度优先搜索
	void _DFS( vertex );						//以vertex为源开始深度优先搜索
	void _BFS(void);							//广度优先搜索
	~_graph(void){ delete [] _sorce; };
private:
	vertex * _sorce;							//用于存储所有的节点
	unsigned _size;								//节点数目
};
_graph::_graph(void)
{
	cout<<"请输入节点总数目:"<<endl;
	cin>>_size;									//输入节点总数
	_sorce = new vertex[_size];					//申请空间
	for( unsigned i = 0; i < _size; i++ )
	{
		_sorce[i]._pos = i;						//得到此节点的索引
		cout<<"请输入"<<i + 1<<"号节点的内容"<<endl;
		cin>>_sorce[i]._data;					//节点内容
		cout<<"与其邻接的节点数目:"<<endl;
		cin>>_sorce[i].adj_ver_numb;			//与此节点邻接的节点数目
		_sorce[i].adj = new unsigned[_sorce[i].adj_ver_numb];
		cout<<"他们依次是几号节点:"<<endl;
		for( unsigned j = 0; j < _sorce[i].adj_ver_numb; j++ )//与此节点邻接的节点
		{
			cin>>*( _sorce[i].adj + j );
			*( _sorce[i].adj + j )  = *( _sorce[i].adj + j ) - 1;
		}
	}
}
void _graph::_initial(void)						//初始化，使所有的节点都处于未被访问的状态
{
	for( unsigned i = 0; i < _size; i++ )
		_sorce[i]._new = true;
}
void _graph::_DFS(void)							//深度优先搜索
{
	cout<<"深度优先搜索序列如下:"<<endl;
	_initial();
	for( unsigned i = 0; i < _size; i++ )
		if( _sorce[i]._new == true )			//找到一个未访问过的节点，从它开始深度优先搜索
			_DFS( _sorce[i] );
	cout<<endl;
}
void _graph::_DFS( vertex s )					//以s为源开始深度优先搜索
{

	cout<<s._data;
	_sorce[s._pos]._new = false;
	for( unsigned i = 0; i < s.adj_ver_numb; i++ )
		if( _sorce[ s.adj[i] ]._new == true )
			_DFS( _sorce[ s.adj[i] ] );
}
void _graph::_BFS(void)							//广度优先搜索
{
	cout<<"广度优先搜索序列如下:"<<endl;
	_initial();
	_queue<vertex, 32> Queue;
	Queue._enQueue( _sorce[0] );				//第一个节点进队列
	while( ! Queue._empty() )
	{
		vertex temp = Queue._deQueue();			//队列首元素出列
		if( _sorce[temp._pos]._new == true )	//如果它未被访问过
		{
			cout<<temp._data;					//输出
			_sorce[temp._pos]._new = false;		//设置其状态为已访问过
		}
		for( unsigned i = 0; i < temp.adj_ver_numb; i++ )
			if( _sorce[ temp.adj[i] ]._new == true )//将与此节点邻接的而且未被访问过节点进队列
				Queue._enQueue( _sorce[ temp.adj[i] ] );
	}
	cout<<endl;
}
int main()
{
	_graph Graph;	
	Graph._DFS();	
	Graph._BFS();
	return 0;
}