二十三、图的遍历（BFS和DFS）

一、概念

  图的遍历(Traversing Graph)从某一顶点出发，访问图中所有顶点，且使每一顶点仅被访问一次。与树的遍历不同的是，图的遍历需要处理两种特殊情况：一是从某一顶点出发进行遍历时，可能访问不到所有其他顶点，比如非连通图；二是有些图存在回路，必须保证遍历过程不能因为回路陷入死循环。

  图的遍历是解决图的许多应用问题的基础，如路径问题、连通性问题等。图的遍历有两种基本方法：深度优先遍历（Depth-First Search, DFS）和广度优先遍历（Breadth-First Search, BFS）。

二、深度优先遍历

深度优先遍历以“深度”作为第一关键词，沿着一条路径直到无法继续前进，才退回到路径上离当前顶点最近的还存在未访问分支顶点的岔道口，并前往访问那些未访问分支顶点，直到遍历完整个图。

过程如下：

1. 从图中某个顶点 $v$ 出发，访问 $v$ 。
2. 找出刚访问过的顶点的第一个未被访问的邻接点，访问该顶点。以该顶点为新顶点，重复此步骤，直至刚访问过的顶点，没有未被访问的邻接点为止。
3. 返回前一个访问过的且仍有未被访问的邻接点的顶点，找出该顶点的下一个未被访问的邻接点，访问该顶点。
4. 重复步骤2和3，直至图中所有顶点都被访问过，搜索结束。

邻接矩阵

1.连通图的深度优先遍历

Status DFS_M(MGraph G, int k, Status(*visit)(int))
{	//从连通图G的k顶点出发进行深度优先遍历，图G采用邻接数组存储结构
	int i;
	if (visit(k) == ERROR)					 //访问 k 顶点
		return ERROR;			
	G.tags[k] = VISITED;
	for (i = FirstAdjVex_M(G, k); i >= 0; i = NextAdjVex_M(G, k, i))
	{
		if (G.tags[i] == UNVISITED)			 //位序为i的邻接顶点未被访问过
			if (DFS_M(G, i, visit) == ERROR) //对 i 顶点递归深度遍历
				return ERROR;				
	}
	return OK;
}

2.图的深度优先遍历

Status DFSTraverse_M(MGraph G, Status(*visit)(int))
{	//深度优先遍历采用邻接数组存储结构的图G
	int i;
	for (i = 0; i < G.n; i++)
		G.tags[i] = UNVISITED;			//初始化标志数组
	for (i = 0; i < G.n; i++)
		if (G.tags[i] == UNVISITED)		//若i顶点未访问，则以其为起点进行深度优先遍历
			if (DFS_M(G, i, visit) == ERROR)
				return ERROR;
	return OK;
}