数据结构 图 深度优先遍历（DFS） 广度优先遍历（BFS）

图的邻接表表示法看这里

首先定义必要的辅助数组和函数

bool visited[MAX_VERTEX_NUM];//标志是否访问过

template<typename VertexType, typename InfoType>
int firstAdjVex(ALGraph<VertexType, InfoType>ALG, int vIndex)//寻找第一个邻接点，未找到返回-1
{
	if (vIndex < 0 || vIndex > ALG.vexnum - 1)
		return -1;
	return ALG.vertices[vIndex].firstarc->adjvex;
}

template<typename VertexType, typename InfoType>
int nextAdjVex(ALGraph<VertexType, InfoType>ALG, int vIndex, int curAdjIndex)//寻找v相对于cur的下一个邻接点，未找到返回-1
{
	if (vIndex < 0 || vIndex > ALG.vexnum - 1)
		return -1;
	ArcNode<InfoType>* p = ALG.vertices[vIndex].firstarc;
	while (p->adjvex != curAdjIndex && p)
		p = p->nextarc;
	if (!p)
		return -1;
	if (p->nextarc)
		return p->nextarc->adjvex;
	else
		return -1;
}

template<typename VertexType,typename InfoType>
Status print(ALGraph<VertexType, InfoType>ALG, int v)//打印信息
{
	cout << ALG.vertices[v].data << " ";
	return OK;
}

深度优先遍历（DFS）

图的深度优先遍历类似于树的前序遍历，当访问一个顶点后，立即访问该顶点未访问过的第一个邻接顶点，直到第一个邻接顶点已经完成深度优先遍历后，再依次对其余未访问的邻接顶点进行深度优先遍历，适合使用递归求解

首先初始化标志数组，开始对每一个连通分量进行深度优先遍历。对某个连通分量进行深度优先遍历时，首先访问第一个顶点，然后对其第一个邻接顶点进行深度优先遍历，显然是一个递归过程，只有当第一个邻接顶点完成了深度优先遍历后，继续对下一个邻接顶点进行深度优先遍历

具体实现：

template<typename VertexType,typename InfoType>
Status DFS(ALGraph<VertexType, InfoType>ALG, int i, Status(*visit)(ALGraph<VertexType, InfoType>ALG, int v))
{//递归深度优先遍历一个连通分量
	visit(ALG, i);//访问
	visited[i] = true;//标志
	int index = firstAdjVex(ALG, i);//寻找i的第一个邻接点
	while (index >= 0)
	{
		if(!visited[index])
			DFS(ALG, index, visit);//深度优先遍历i的第一个邻接点
		index = nextAdjVex(ALG, i, index);//遍历下一个邻接点
	}
	return OK;
}

template<typename VertexType,typename InfoType>
Status DFSTraverse(ALGraph<VertexType, InfoType>ALG, Status(*visit)(ALGraph<VertexType, InfoType>ALG, int v))
{//深度优先遍历
	for (int i = 0; i < MAX_VERTEX_NUM; i++)//初始化
		visited[i] = false;
	for (int i = 0; i < ALG.vexnum; i++)//遍历所有连通分量
	{
		if (!visited[i])
			DFS(ALG, i, visit);//开始深度优先遍历
	}
	return OK;
}

广度优先遍历（BFS）

图的广度优先遍历类似于树的层序遍历，当访问完一个顶点之后，访问该顶点的全部邻接顶点，然后再广度优先遍历访问这些邻接顶点的所有邻接顶点，需要借助队列实现

队列参考这里

首先初始化标志数组，然后访问第一个顶点并入队；每次当队列非空时，出队一个元素，访问并入队该顶点的所有未被访问过的邻接顶点

具体实现：

template<typename VertexType, typename InfoType>
Status BFSTraverse(ALGraph<VertexType, InfoType>ALG, Status(*visit)(ALGraph<VertexType, InfoType>ALG, int v))
{//广度优先遍历
	SqQueue<int> Q;
	initSqQueue(Q);
	int index = 0;
	for (int i = 0; i < MAX_VERTEX_NUM; i++)//初始化
		visited[i] = false;
	for (int i = 0; i < ALG.vexnum; i++)//广度优先遍历每一个连通分量
	{
		if (!visited[i])
		{
			visit(ALG, i);//访问
			visited[i] = true;//标志
			enSqQueue(Q, i);//入队
			while (!isSqQueueEmpty(Q))
			{
				deSqQueue(Q, index);//出队
				for (int j = firstAdjVex(ALG, index); j >= 0; j = nextAdjVex(ALG, index, j))
				{//遍历index的所有邻接点，访问、标志并入队所有未访问的邻接点
					if (!visited[j])
					{
						visit(ALG, j);//访问
						visited[j] = true;//标志
						enSqQueue(Q, j);//入队
					}
				}
			}
		}
	}
	return OK;
}