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

深度优先遍历

  首先我们说一下邻接点的定义，对于无向图，如果两个顶点之间相互连接，那么它们互称为邻接点。

  深度优先遍历支持从指定的结点开始遍历。深度优先遍历，也称作深度优先搜索，缩写为DFS。深度优先遍历从某个顶点v出发，访问此顶点，然后从v的未被访问的邻接点触发深度优先遍历图，直至所有和v有路径想通的顶点都被访问到。

  上面这段话听起来有点官方还有点笼统，不太好理解，所以我们通俗一点来说明这个问题。

  所谓深度优先遍历就是从某个指定的结点开始，先访问它，然后遍历存储顶点的数组，如果碰到它的邻接点，并且这个邻接点没有被访问过，那么就递归调用这个函数来访问它，然后递归函数又会在访问完它之后，去递归访问它的邻接点......等到递归函数第一次出栈之后又会去访问上一个访问的结点的下一个邻接点......一直这样层层递归出栈，就可以访问到所有的结点，这样就达到了深度优先的遍历结果。

看看代码

  在实现深度优先遍历之前，我们得先实现一个内部私有的功能函数bool getValueFromMatrix(int row, int col, int& val),这个函数的作用是得到邻接矩阵中row行col列的值，将其存放在val里

//对这个矩阵的读操作，读取某一个值，将值存放在val中
bool getValueFromMatrix(int row, int col, int& val)
{
	if (row < 0 || row >= m_iCapacity || col < 0 || col >= m_iCapacity)
		return false;
	val = m_pMatrix[row * m_iCapacity + col];
	return true;
}

    //深度优先遍历
    void depthFirstTraverse(int nodeIndex)//从指定的下标开始遍历
    {
	int value = 0;
	cout << m_pNodeArray[nodeIndex].m_cdata << " ";			//访问这个顶点
	m_pNodeArray[nodeIndex].m_bIsVisited = true;			//设置这个顶点为访问过的

	for (int i = 0; i <= m_iCapacity; i++)
	{
	    getValueFromMatrix(nodeIndex, i, value);			//得到近邻矩阵中的值，表示两个顶点有没有连在一起
	    if (value)			//value不为0，说明连在一起了
	    {
		if (!m_pNodeArray[i].m_bIsVisited)		//还要判断是否访问过
			depthFirstTraverse(i);				//递归访问
		else
		    continue;
	    }
	    else
		continue;
	}
    }

广度优先遍历

  广度优先遍历就是先访问一个给定的结点v，然后将它的所有的未被访问过的联通点点存放入一个容器中，然后再依次访问这个容器中的结点，再将刚刚访问过的结点的为访问过的联通点重新存入容器中，重复上述操作，直到所有的顶点都被访问过。

代码实现：

//广度优先遍历
    void breadthFirstTraverse(int nodeIndex)
    {
	//先访问第一个起始顶点
	cout << m_pNodeArray[nodeIndex].m_cdata << " ";
	m_pNodeArray[nodeIndex].m_bIsVisited = true;
		
	vector<int> curVec;
	curVec.push_back(nodeIndex);			//将访问过的第一层的顶点索引存放进数组，传给函数

	breadthFirstTraverseImp(curVec);
    }

对于里面内部函数breadthFirstTraverseImp(curVec)的实现：

void breadthFirstTraverseImp(vector<int>preVec)
{
	int value = 0;
	vector<int> curVec; //每次递归进入这个函数后，这个容器都是新的，里面没有任何元素，因为它属于局部变量

	for (int i = 0; i < (int)preVec.size(); i++)		//上层访问过的顶点
	{
		for (int j = 0; j < m_iCapacity; j++)
		{
			//得到近邻矩阵中的值，表示两个顶点有没有连在一起，主要是为了找和上层访问过的顶点连在一起的
			getValueFromMatrix(preVec[i], j, value);	
			if (value)
			{
				if (!m_pNodeArray[j].m_bIsVisited)//没有访问过
				{
					//两个if同时满足表示，既是和上层访问过的顶点连在一起的，又是自身没有被访问过的，即是下面一层的
					cout << m_pNodeArray[j].m_cdata << " ";
					m_pNodeArray[j].m_bIsVisited = true;

					curVec.push_back(j);
				}
					
				else
					continue;
			}
			else
				continue;
		}
	}
	if (curVec.size() == 0)
	{
		return;
	}
	else
		breadthFirstTraverseImp(curVec);
}

  其实这里也可以使用队列来存放结点，这样的话就不需要用递归了

void breadthFirstTraverseImp(queue<int>preQue)	//queue里存放的是结点的下标值
{
	int value = 0;
	while(!preQue.Isempty())
	{
		int elem = preQue.dequeue();
		cout << m_pNodeArray[elem].m_cdata << " ";	//访问队列头结点结点
		m_pNodeArray[j].m_bIsVisited = true;	//设置为访问过的
		for(int j = 0; j < m_iCapacity; j++)
		{
			getValueFromMatrix(elem, j, value);
			if (value)
				{
					if (!m_pNodeArray[j].m_bIsVisited)//没有访问过
					{
						m_pNodeArray[j].m_bIsVisited = true;	//设置为访问过的
						preQue.enqueue(j);	//入队操作
					}
					else
						continue;
				}
			else
				continue;
		}
		
	}
}