#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;
}