深度优先查找和广度优先查找

5.2和5.3节讨论图问题的一些重要算法，他们是减一技术的具体应用。许多图的算法用一种系统的方式来对图的顶点和边进行处理。有两种主要的算法可以进行这种遍历：深度优先查找（DFS）和广度优先查找（BFS）。它们的主要任务是访问顶点和遍历图的边。

深度优先查找

深度优先查找从任意顶点开始访问图的顶点，并且把该顶点标记为已访问。在每次迭代的时候，算法紧接着处理与当前顶点邻接的未访问顶点。（这里的当前顶点可以任意选择。实际应用中，选择未访问候选顶点是由图的数据结构决定的。在例子中，总是根据顶点的字母顺序来选择顶点）。

访问顶点的过程一直持续，直到遇到一个死端——一个无法通向未访问邻接顶点的顶点。在一个死端上，算法沿着来路后退一条边，并试着继续从那里访问未访问的顶点。在后退到起始顶点，并且起始顶点也是一个死端的时候，算法最终停了下来。起始顶点所在的连通分量的所有顶点都被访问过了。如果未访问过的顶点仍然存在，算法必需从其中的一个顶点开始，重复上述过程。

用栈来跟踪深度优先查找是比较方便的。在第一次访问一个饿顶点的时候，我们把该顶点入栈，表示开始对该点访问，当它称为一个死端的时候，我们把它出栈，表示结束对该顶点的访问.

深度优先查找遍历时构造深度优先查找森林是非常有用的。遍历的初始顶点作为森林中第一棵树的根。如果第一次遇到一个新的未访问顶点，它是从哪个顶点被访问到的，就把它附加为那个顶点的子女。连续这样两个顶点的边称为树向边,所有这种边的集合构成了一个森林。算法会遇到一条指向已访问顶点的边，并且整个顶点不是它的直接前趋，即它在树中的父母，我们把这种边称为回边,这条边把一个顶点和它的非父母祖先连在了一起。图(a)给出了一个深度优先查找遍历的例子。

(b)为遍历栈，第一个下标数字指出某个顶点被访问到的顺序，也就是入栈；第二个下标数字指出该顶点变成死端的顺序，也就是出栈。

(c)为相应的深度优先查找森林。树向边用实线表示，回边用虚线表示。

这里有一个深度优先查找的伪代码。

算法 DFS(G)
    //实线给定图的深度优先查找遍历
    //输入：图G=<V,E>
    //输出：图G的顶点，按照被DFS遍历的第一次访问到的先后次序，用连续的整数标记
    将V中的每个顶点标记为0，表示还“未访问”
    count <- 0
    for each vertex v in V do
        if v is marked with 0
            dfs(v)

dfs(v)
//递归访问所有和v相连接的未访问顶点，然后按照全局变量count的值
//根据遇到它们的先后顺序，给它们赋上相应的数字
count <- count + 1; mark v with count
for each vertex with V adjacent to v do
    if w is marked with 0
        dfs(w)

为认识到该算法的功效和深度，我们根据它的邻接矩阵和邻接链表来跟踪算法的操作。

深度优先查找的效率如何呢？

DFS森林也值得我们研究。首先声明，它实际上不是一个森林。它就如给定图，图的边被DFS遍历分为不相交的两类：树向边和回边。

事实证明，DFS遍历和它提供的图的类森林表示法，对于开发某些高效算法是非常有帮助的，这些算法主要用来研究图的许多重要特性。注意，DFS产生的两种顶点序列：第一次访问顶点的次序（入栈）和顶点成为死端的次序（出栈）。这两种次序在性质上是不同的，不同的应用可以按照需要利用这两种不同的次序。

DFS重要的基本应用有检查图的连通性和无环性。我们这样检查一个图的连通性：从任意一个顶点开始DFS遍历，在该算法停下来以后，检查一下是否所有的顶点都被访问过了。如果都访问过了，那么这个图是连通的；否则，它是不连通的。一般来说，我们可以用DFS来找到一个图的连通分量。

如果要检查一个图中是否包含回路，可以利用图的DFS森林形式的表示法。如果DFS森林不包含回边，这个图显然是无回路的。如果从某些顶点u到它的祖先v之间有一条回边（例如，在图(c)从d到a的回边），则该图有一个回力，这个回路是由DFS森林中从v到u的路径上的一系列树向边以及从u到v的回边构成的。

DFS有一个复杂的应用是求图的关节点，从图中移走一个顶点和所有它附带的边之后，图被分为若干个不相交的部分，这样的顶点是图的关节点。

广度优先查找

如果说深度优先查找遍历表现出来的是一种勇气（该算法尽可能地离“家”远些），广度优先查找遍历出来的则是一种谨慎。它按照同心圆的方式，首先访问所有和初始顶点邻接的顶点，然后是离它两条边的所有未访问的顶点，以此类推，直到所有与初始顶点同在一个连通分量中的顶点都访问过了为止。如果仍然存在未被访问的顶点，该算法必需从图的其他连通分量中的任意顶点重新开始。

使用队列来跟踪广度优先查找的操作是比较方便的。该队列先从遍历的初始顶点开始，将该顶点标记为已访问。在每次迭代的时候，找出所有和队头顶点邻接的未访问顶点，把它们标记未已访问，再把它们入队；然后将对头顶点从队列中移去。

和DFS遍历类似，在BFS遍历的同时，构造一个所谓的广度优先查找森林是有意义的。遍历的初始顶点作为这样一个森林中第一棵树的根。无论何时，只要第一次遇到一个新的未访问顶点，它是从哪个顶点被访问到的，就把它附加为哪个顶点的子女。连接这样两个顶点的边称为树向边.如果一条边指向的是一个曾经访问过的顶点，并且这个顶点并不是它的直接前趋，即它在树中的父母，这种边被称为交叉边.

图(a)给出了一个广度优先查找遍历的例子。

图(b)为遍历队列，其中的数字指出某个顶点被访问到的顺序，也就是入队(或出队)。

图(c)为广度优先查找树，树向边用实线表示，交叉边用虚线表示。

这里有一个广度优先查找的伪代码。

算法 BFS(G)
    //实线给定图的广度优先查找遍历
    //输入：图G＝<V,E>
    //输出：图G的顶点，按照被BFS遍历访问到的先后次序，用连续的整数标记
    将V中的每个顶点标记为0，表示还“未访问”
    count <- 0
    for each vertex v in V do
        if v is marked with 0
            bfs(v)

bfs(v)
//访问所有和v相连续的未访问顶点，然后按照全局变量count的值
//根据访问它们的先后顺序，给它们赋上相应的数字
count <- count+1; mark v with count and initialize a queue with v
while the queue is not empty do
    for each vertex w in V adjacent to the front's vertex v do
        if w is marked with 0
            count <- count+1; mark w with count
            and w to the queue
remove vertex v from the front of the queue

至于说BFS森林的结构，它也可能具有两种不同类型的边：树向边和交叉边。树向边是一种通向原先未访问顶点的边。交叉边把顶点和那些已访问顶点相连，但和DFS树中的回边不同，它还连接BFS树中同层或者相邻层中的兄弟顶点。

最后指出，BFS也可以用来检查图的连通性和无环性，做法在本质上和DFS是一样的。它不适用于求关节点，但可以来处理一些DFS无法处理的情况。例如，BFS可以用来求两个给定顶点间边的数量最少的路径。我们从两个给定的顶点中的一个开始BFS遍历，一旦访问到了另一个顶点就结束。从BFS树的根到第二个给定的顶点间的最简单路径就是我们所求得的路径。

例如，图3.12中，在顶点a和g之间的所有路径中，路径a-b-c-g具有最少的边数。

表3.1总结了深度哟线查找和广度优先查找的主要事实。