1.3 图的遍历

图的遍历 （Traversing Graph）是指从图中某一顶点出发，按照某种遍历方法访问图中的全部顶点，且每个顶点仅被访问一次。图的遍历是很多图算法的基础。本节介绍两种主要的遍历方法： 广度优先搜索 和 深度优先搜索 。这两种遍历方式对无向图和有向图都适用。

1.3.1 广度优先搜索

假设初始时，图 G 的所有顶点均未被访问过，在图 G 中任选一个顶点 v _i 作为起始点，则广度优先搜索（Breadth-First Search，BFS）的基本思想是：

①首先访问起始顶点 v _i ，接着由 v _i 出发，依次访问 v _i 的各个未访问过的邻接顶点 w ₁ ， w ₂ ，…， w _i ；

②然后依次访问 w ₁ ， w ₂ ，…， w _i 的所有未被访问过的邻接顶点；

③以此类推，直至图中所有已被访问的顶点的邻接点都被访问到；

④若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作为起始点，重复上述过程，直到图中所有顶点都被访问到为止。

实际上，广度优先搜索遍历图的过程是以 v 为起始点，由近至远依次访问和 v 有路径相通且路径长度为1，2，…的顶点。

对如图1-20所示的无向图 G ₇ ，从顶点 v ₁ 出发的广度优先搜索的过程为：首先访问顶点 v ₁ ，然后访问与它相邻接的顶点 v ₂ 、 v ₃ 、 v ₄ ，接着再依次访问这三个顶点的邻接点中未访问的顶点 v ₅ 、 v ₆ ，最终得到顶点被访问的顺序是 v ₁ 、 v ₂ 、 v ₃ 、 v ₄ 、 v ₅ 、 v ₆ 。

1.3.2 深度优先搜索

假设初始时，图 G 的所有顶点均未被访问过，在图 G 中任选一个顶点 v _i 作为起始点，则深度优先搜索（Depth-First Search，DFS）的基本思想是：

①首先访问起始顶点 v _i ；

②然后从 v _i 的未被访问的邻接点中依次选择顶点 w ，若 w 未曾被访问，则以 w 为新的起始点继续进行深度优先搜索，以此类推，直到图中与 v _i 有路径相通的顶点全部被访问到；

③若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作为始点，重复①和②，直至图中所有顶点都被访问到为止。

以如图1-20所示的无向图 G ₇ 为例说明深度优先搜索的过程：从顶点 v ₁ 出发，访问完 v ₁ 之后，选择邻接顶点 v ₂ ，访问完 v ₂ 之后，退回到 v ₁ ，选择 v ₁ 的下一个邻接顶点 v ₃ 。因为 v ₃ 未被访问，所以可以从 v ₃ 出发进行深度优先搜索，首先选择 v ₃ 的一个邻接顶点 v ₅ ，访问完 v ₅ 之后，退回到 v ₃ ，访问其另一个邻接顶点 v ₆ ，之后退回到 v ₁ ，访问 v ₁ 的最后一个邻接顶点 v ₄ 。由此得到的顶点访问序列为 v ₁ 、 v ₂ 、 v ₃ 、 v ₅ 、 v ₆ 、 v ₄ 。 NDmHsB4FZKA3kXmh3oOoxKdigBhKN70rmpnBgatP7COgi8NqiHDc+ilyy0eT40/8