图的广度优先遍历和深度优先遍历

给定一个图G和其中任意一个顶点v0，从v0出发，沿着图中各边访问图中的所有顶点，且每个顶 点仅被遍历一次。"遍历"即对结点进行某种操作的意思。

1. 广度优先遍历

广度优先遍历类似于二叉树的层序遍历，可以利用队列来实现。对于利用邻接表存储的图，我们给定任意一顶点，将与改顶点连接的链表遍历即可，一层一层的遍历。但是要注意可能会出现重复遍历，所以我们要添加标记。

广度优先遍历的实现

void BFS(const T& value)
	{
		queue<T>q;
		vector<bool> state;
		state.resize(_v.size(), false);  //标记顶点的状态（是否被遍历）

		int index = Getsign(value);
		q.push(index);
		_BFS(q, state);
	
		//遍历非连通图的顶点，即遗漏的顶点
		for (int i = 0; i < _v.size(); i++)
		{
			if (state[i] == false)
			{
				q.push(i);
				_BFS(q, state);
			}
			
		}

	}
	void _BFS(queue<T>& q, vector<bool>& state)
	{
         while (!q.empty())
		{
			int index = q.front();
			if (state[index] != true)
			{
				cout << _v[index] << " ";
				state[index] = true;

				PNode pcur = _Edge[index];
				while (pcur)
				{
					q.push(pcur->_dest);
					pcur = pcur->_PNext;

				}
			}
			q.pop();
		}
	}

 

2. 深度优先遍历

 

所谓的深度优先是指像拉抽屉一样不断的深入。对于图的深度优先遍历我们可以化大的问题为小的问题，化整为零，不断递归。

深度优先遍历实现：

	void DFS(const T& value)
	{
		int size = _v.size();
		size_t index = Getsign(value);
	    vector<bool> state;
		state.resize(size, false);
		_DFS(index, state);

		//遍历遗漏的顶点
		for (size_t i = 0; i < size; i++)
		{
			if (state[i]==false)
			  _DFS(i, state);
		}
	}
	void _DFS(size_t index, vector<bool>& state)
	{
		
		cout << _v[index] << " ";
		state[index] = true;
		
		PNode Pcur = _Edge[index];
		while (Pcur)
		{
			if (state[Pcur->_dest] != true)
			{
                _DFS(Pcur->_dest, state);	
			}
			Pcur = Pcur->_PNext;
		}
		  
	
	}