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

一、概念

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

图的遍历是解决图的许多应用问题的基础，如路径问题、连通性问题等。图的遍历有两种基本方法：

深度优先遍历（Depth-First Search, DFS）
广度优先遍历（Breadth-First Search, BFS）

二、深度优先遍历

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

过程如下：

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

DFS的具体实现

DFS遍历图的基本思路就是将经过的顶点设置为已访问，在下次递归碰到这个顶点的时就不再去处理，直到整个图的顶点都被标记为已访问。

动图演示

邻接矩阵

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;

}

深度优先搜索遍历的算法分析

在遍历图时，对图中每个顶点至多调用一次DFS函数，因为一旦某个顶点被标志成已被访问，就不再从它出发进行搜索。因此，遍历图的过程实质上是对每个顶点查找其邻接点的过程，其耗费的时间则取决于所采用的存储结构。

当用邻接矩阵表示图时，查找每个顶点的邻接点的时间复杂度为 $O({n^2})$，其中 $n$ 为图中顶点数。
当以邻接表做图的存储结构时，查找邻接点的时间复杂度为 $O(e)$，其中 $e$ 为图中边数。由此，当以邻接表做存储结构时，深度优先搜索遍历图的时间复杂度为 $O(n+e)$。

三、广度优先遍历

广度优先遍历，类似于树的按层次遍历的过程，以“广度”作为关键词，每次以扩散的方式向外访问顶点。

过程如下：

从图中某个顶点 $v$ 出发，访问 $v$ 。
依次访问 $v$ 的各个未曾访问过的邻接点。
分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问。重复步骤3，直至图中所有已被访问的顶点的邻接点都被访问到。

BFS的具体实现

使用BFS遍历图的基本思想是建立一个队列，并把初始顶点加入队列，此后每次都取出队首顶点进行访问，并把从该顶点出发可以到达的未曾加入过队列（而不是未访问）的顶点全部加入队列，直到队列为空。

动图演示

邻接表

1.图的广度优先遍历

Status BFSTraverse_AL(ALGraph G, Status(*visit) (int))

{	//广度优先遍历采用邻接表存储结构的图G

	int i, j, k;

	AdjVexNodeP p;

	LQueue Q;

	InitQueue_LQ(Q);					//初始化链队列Q

	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 (visit(i) == ERROR)

				return ERROR;

			G.tags[i] = VISITED;

			EnQueue_LQ(Q, i);				//访问 i 顶点，并入队

			while (DeQueue_LQ(Q, k) == OK)	//出队元素到 k

			{

				for (j = FirstAdjVex_AL(G, k, p); j >= 0; j = NextAdjVex_AL(G, k, p))

					//依次判断 k 顶点的所有邻接顶点j, 若未曾访问，则访问它，并入队

				{

					if (G.tags[j] == UNVISITED)

					{

						if (visit(j) == ERROR)

							return ERROR;

						G.tags[j] = VISITED;

						EnQueue_LQ(Q, j);

					}

				}

			}

		}

	return OK;

}

广度优先搜索遍历的算法分析

由算法可知，每个顶点至多进一次队列。遍历图的过程实质上是通过边找邻接点的过程，因此广度优先搜索遍历图的时间复杂度和深度优先搜索遍历相同。两种遍历方法的不同之处仅仅在于对顶点访问的顺序不同。

当用邻接矩阵表示图时，查找每个顶点的邻接点的时间复杂度为 $O({n^2})$，其中 $n$ 为图中顶点数。
当以邻接表做图的存储结构时，广度优先搜索遍历图的时间复杂度为 $O(n+e)$。

巴特西

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

一、概念

二、深度优先遍历

DFS的具体实现

动图演示

邻接矩阵

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

2.图的深度优先遍历

深度优先搜索遍历的算法分析

三、广度优先遍历

BFS的具体实现

动图演示

邻接表

1.图的广度优先遍历

广度优先搜索遍历的算法分析

最新文章

热门文章