1.2.2 图的遍历

图的遍历是指从图中的某一顶点出发，按照某种搜索算法沿着图中的边对图中的所有顶点访问一次且仅访问一次。图的遍历主要有两种算法：深度优先搜索（DFS，Depth-First-Search）和广度优先搜索（BFS，Breadth-First-Search）。图的遍历是一种重要的图检索手段，深度优先搜索与广度优先搜索给出了相应的算法基础。

深度优先搜索是一个递归算法，有回退过程。其算法思想是：从图中某一顶点vi开始，由vi出发，访问它的任意一个邻居w1；再从w1出发，访问w1的所有邻居中未被访问过的顶点w2；然后再从w2出发，依次访问，直到出现某顶点不再有邻居未被访问过。接着，回退一步，回退到前一次刚访问过的顶点，看是否还有其他未被访问过的邻居，如果有，则访问该邻居，之后再从该邻居出发，进行与前面类似的访问；如果没有，就再回退一步进行类似访问。重复上述过程，直到该图中所有顶点都被访问过为止。以图1-7为例，我们可以得到如下深度优先搜索序列：v1→v2→v4→v5→v3。

广度优先搜索是一个分层的搜索过程，没有回退过程，其算法思想是：从图中某一顶点vi开始，由vi出发，依次访问vi的所有未被访问过的邻居w1，w2，…，wn；然后再顺序访问w1，w2，…，wn的所有还未被访问过的邻居，如此一层层执行下去，直到图中所有顶点都被访问到为止。以图1-7为例，我们可以得到如下广度优先搜索序列：v1→v2→v3→v4→v5。