6.3 图的遍历

广度优先搜索与深度优先搜索的过程、复杂度、生成树，以及用遍历判断连通性。

图的遍历

图的遍历是指从图中的某一顶点出发，按照某种搜索方法沿着图中的边对图中的所有顶点访问一次，且仅访问一次。注意到树是一种特殊的图，所以树的遍历实际上也可视为一种特殊的图的遍历。

图的任意一个顶点都可能和其余的顶点相邻接，所以在访问某个顶点后，可能沿着某条路径搜索又回到该顶点上。为避免同一顶点被访问多次，在遍历图的过程中，必须记下每个已访问过的顶点，为此可以设一个辅助数组 visited[] 来标记顶点是否被访问过。

广度优先搜索（BFS）

广度优先搜索类似于二叉树的层序遍历算法。基本思想是：首先访问起始顶点 $v$，接着由 $v$ 出发，依次访问 $v$ 的各个未访问过的邻接顶点 $w_1, w_2, \ldots, w_i$，然后依次访问 $w_1, w_2, \ldots, w_i$ 的所有未被访问过的邻接顶点；再从这些访问过的顶点出发，访问它们所有未被访问过的邻接顶点……直至图中所有顶点都被访问过为止。

BFS 是一种分层的查找过程，每向前走一步可能访问一批顶点，不像 DFS 那样有往回退的情况，因此它不是一个递归的算法。为了实现逐层的访问，算法必须借助一个辅助队列。

1void BFS(Graph G, int v) {
2    visit(v);
3    visited[v] = true;
4    EnQueue(Q, v);
5    while (!isEmpty(Q)) {
6        DeQueue(Q, v);              // 队头顶点出队
7        for (w = FirstNeighbor(G, v); w >= 0;
8             w = NextNeighbor(G, v, w))
9            if (!visited[w]) {      // w 为 v 尚未访问的邻接顶点
10                visit(w);
11                visited[w] = true;
12                EnQueue(Q, w);
13            }
14    }
15}
16void BFSTraverse(Graph G) {
17    for (i = 0; i < G.vexnum; ++i) visited[i] = false;
18    for (i = 0; i < G.vexnum; ++i)  // 处理非连通图
19        if (!visited[i]) BFS(G, i);
20}

BFS 求解单源最短路径：若图 $G = (V, E)$ 为非带权图，定义从顶点 $u$ 到顶点 $v$ 的最短路径 $d(u, v)$ 为从 $u$ 到 $v$ 的任何路径中最少的边数。使用 BFS，可以求解一个满足上述定义的非带权图的单源最短路径问题，这是由广度优先搜索总是按照距离由近到远来遍历图中每个顶点的性质决定的。

广度优先生成树：在广度遍历的过程中，我们可以得到一棵遍历树，称为广度优先生成树（动画中的绿色粗边）。需要注意的是，同一个图的邻接矩阵存储表示是唯一的，故其广度优先生成树也是唯一的；但由于邻接表存储表示不唯一，故其广度优先生成树也是不唯一的。

深度优先搜索（DFS）

与广度优先搜索不同，深度优先搜索类似于树的先序遍历。如其名称中所暗含的意思一样，这种搜索算法所遵循的策略是尽可能”深”地搜索一个图。

基本思想：首先访问图中某一起始顶点 $v$，然后由 $v$ 出发，访问与 $v$ 邻接且未被访问的任意一个顶点 $w_1$，再访问与 $w_1$ 邻接且未被访问的任意一个顶点 $w_2$……重复上述过程。当不能再继续向下访问时，依次退回到最近被访问的顶点，若它还有邻接顶点未被访问过，则从该点开始继续上述搜索过程，直至图中所有顶点均被访问过为止。

1void DFS(Graph G, int v) {
2    visit(v);
3    visited[v] = true;
4    for (w = FirstNeighbor(G, v); w >= 0;
5         w = NextNeighbor(G, v, w))
6        if (!visited[w])            // w 为 v 尚未访问的邻接顶点
7            DFS(G, w);
8}
9void DFSTraverse(Graph G) {
10    for (v = 0; v < G.vexnum; ++v) visited[v] = false;
11    for (v = 0; v < G.vexnum; ++v)  // 处理非连通图
12        if (!visited[v]) DFS(G, v);
13}

图的遍历与图的连通性

图的遍历算法可以用来判断图的连通性：

• 对于无向图，若无向图是连通的，则从任意一个结点出发，仅需一次遍历就能够访问图中的所有顶点；若无向图是非连通的，则从某一个顶点出发，一次遍历只能访问到该顶点所在连通分量的所有顶点。调用 BFS/DFS 的次数 = 连通分量数。
• 对于有向图，若从初始点到图中的每个顶点都有路径，则能够访问到图中的所有顶点，否则不能访问到所有顶点。有向图调用 BFS/DFS 的次数不一定等于强连通分量数。

在动画中切换到”有向图”，从不同起点出发，观察 BFSTraverse 需要调用几次 BFS。

即时练习