图的遍历：广度优先搜索与深度优先搜索详解
图的遍历：广度优先搜索与深度优先搜索详解
图的遍历是计算机科学和数据结构课程中的重要知识点，包括图的遍历概述、广度优先搜索（BFS）和深度优先搜索（DFS）的原理、过程及性能分析等内容。本文将详细介绍图的遍历相关知识。
图的遍历概述
图的遍历是指从图中的某一项点出发，按照某种搜索方法沿着图中的边对图中的所有顶点访问一次，且仅访问一次。注意到树是一种特殊的图，所以树的遍历实际上也可视为一种特殊的图的遍历。
图的遍历算法的重要性
图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。
图的遍历与树的遍历的区别
图的遍历比树的遍历要复杂得多，因为图的任意一个顶点都可能和其余的顶点相邻接，所以在访问某个顶点后，可能沿着某条路径搜索又回到该顶点。
图的遍历过程中的注意事项
- 避免重复访问：为避免同一顶点被访问多次，在遍历图的过程中，必须记下每个已访问过的顶点，为此可以设一个辅助数组
visited[]来标记顶点是否被访问过。 - 遍历算法的分类：图的遍历算法主要有两种：广度优先搜索（BFS）和深度优先搜索（DFS）。
- 遍历结果的不唯一性：图的遍历结果顺序是不唯一的，跟选择的起始结点和所求邻接结点的顺序有关。
广度优先搜索（BFS）
BFS 概述
广度优先搜索（Breadth-First-Search, BFS）类似于二叉树的层次遍历算法。基本思想是：首先访问起始顶点v，接着由v出发，依次访问v的各个未访问过的邻接顶点w1, w2, ..., wr，然后依次访问w1, w2, ..., wr的所有未被访问过的邻接顶点；再从这些访问过的顶点出发，访问它们所有未被访问过的邻接顶点，直至图中所有顶点都被访问过为止。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作为始点，重复上述过程，直至图中所有顶点都被访问到为止。
BFS 的特点
广度优先搜索遍历图的过程是以v为起始点，由近至远依次访问和v有路径相通且路径长度为1, 2, … 的顶点。广度优先搜索是一种分层的查找过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有往回退的情况，因此它不是一个递归的算法。为了实现逐层的访问，算法必须借助一个辅助队列，以记忆正在访问的顶点的下一层顶点。
BFS 遍历过程
假设从顶点a开始访问，a先入队。此时队列非空，取出队头元素a，因为b, c与a邻接且未被访问过，于是依次访问b, c，并将b, c依次入队。队列非空，取出队头元素b，依次访问与b邻接且未被访问的顶点d, e，并将d, e入队（注意：a与b也邻接，但a已置访问标记，所以不再重复访问）。此时队列非空，取出队头元素c，访问与c邻接且未被访问的顶点f, g，并将f, g入队。此时，取出队头元素d，但与d邻接且未被访问的顶点为空，所以不进行任何操作。继续取出队头元素e，将h入队列……最终取出队头元素h后，队列为空，从而循环自动跳出。遍历结果为a b c d e f g h。
BFS 算法的性能分析
无论是邻接表还是邻接矩阵的存储方式，BFS算法都需要借助一个辅助队列Q，n个顶点均需入队一次，在最坏的情况下，空间复杂度为O(|V|)。采用邻接表存储时，查找每个顶点的邻接点所需的时间为O(|V|)，总时间复杂度为O(|V| + |E|)。采用邻接矩阵存储时，总时间复杂度为O(|V|^2)。
BFS 算法求解单源最短路径问题
若图G = (V, E)为非带权图，定义从顶点u到顶点v的最短路径d(u, v)为从u到v的任何路径中最少的边数；若从u到v没有通路，则d(u, v) = ∞。使用BFS，我们可以求解一个满足上述定义的非带权图的单源最短路径问题，这是由广度优先搜索总是按照距离由近到远来遍历图中每个顶点的性质决定的。
广度优先生成树
在广度遍历的过程中，我们可以得到一棵遍历树，称为广度优先生成树。需要注意的是，同一个图的邻接矩阵存储表示是唯一的，所以其广度优先生成树也是唯一的，但因为邻接表存储表示不唯一，所以其广度优先生成树也是不唯一的。
深度优先搜索（DFS）
DFS 概述
深度优先搜索（Depth-First-Search, DFS）是一种尽可能“深”地搜索图的算法。其基本思想如下：
- 借助临时空间：借助n个临时空间来标记结点是否被访问过。
- 访问顶点：首先访问图中的某一顶点v，接着访问v的邻接顶点w，访问w的下一邻接顶点，依次类推，重复上述过程。
- 回溯：当不能再继续向下访问顶点时，依次退回到最近被访问的顶点，如果还有其他邻接顶点没有被访问，则继续从该结点出发开始上述的遍历过程，直到图的所有结点被访问完为止。深度优先遍历相当于二叉树中的前序遍历。
DFS 遍历过程
深度优先搜索的过程如下：
- 首先访问a，并置a访问标记。
- 然后访问与a邻接且未被访问的顶点b，置b访问标记。
- 然后访问与b邻接且未被访问的顶点d，置d访问标记。
- 此时d已没有未被访问过的邻接点，所以返回上一个访问的顶点b，访问与其邻接且未被访问的顶点e，置e访问标记，以此类推，直至图中所有顶点都被访问一次。遍历结果为a b d e h c f g。
DFS 算法的性能分析
DFS算法是一个递归算法，需要借助一个递归工作栈，所以其空间复杂度为O(|V|)。遍历图的过程实质上是通过边查找邻接点的过程，因此两种遍历方式的时间复杂度都相同，不同之处仅在于对顶点访问顺序的不同。采用邻接矩阵存储时，总时间复杂度为O(|V|^2)。采用邻接表存储时，总的时间复杂度为O(|V| + |E|)。
深度优先的生成树和生成森林
与广度优先搜索一样，深度优先搜索也会产生一棵深度优先生成树。当然，这是有条件的，即对连通图调用DFS才能产生深度优先生成树，否则产生的将是深度优先生成森林。与BFS类似，基于邻接表存储的深度优先生成树是不唯一的。
注意事项
图的邻接矩阵表示是唯一的，但对邻接表来说，若边的输入次序不同，则生成的邻接表也不同。因此，对同样一个图，基于邻接矩阵的遍历得到的DFS序列和BFS序列是唯一的，基于邻接表的遍历得到的DFS序列和BFS序列是不唯一的。
图的遍历与图的连通性
图的遍历法可以用来判断图的连通性。对于无向图来说，若无向图是连通的，则从任意一个结点出发，仅需一次遍历就能够访问图中的所有顶点；若无向图是非连通的，则从某一个顶点出发，一次遍历只能访问到该顶点所在连通分量的所有顶点，而对于图中其他连通分量的顶点，则无法通过这次遍历访问。对于有向图来说，若从初始顶点到图中的每个顶点都有路径，则能够访问到图中的所有顶点，否则不能访问到所有顶点。
因此，在BFSTraverse()或DFSTraverse()中添加了第二个for循环，再选取初始点，继续进行遍历，以防止一次无法遍历图的所有顶点。对于无向图，上述两个函数调用BFS(G, i)或DFS(G, i)的次数等于该图的连通分量数；而对于有向图则不是这样，因为一个连通的有向图分为强连通的和非强连通的，它的连通子图也分为强连通分量和非强连通分量，非强连通分量一次调用BFS(G, i)或DFS(G, i)无法访问到该连通分量的所有顶点。