深度优先遍历

1-4.图的处理算法的设计模式

因为我们会讨论大量关于图处理的算法，所以设计的首要目标是将图的表示和实现分离开来。为此，我们会为每个任务创建一个相应的类，
用例可以创建相应的对象来完成任务。类的构造函数一般会在预处理中构造各种数据结构，以有效地响应用例的请求

图处理算法的 API

public class Search{
Search(Graph G, int s)  找到和起点 s 连通的所有顶点
boolean marked(int v)   v 和 s 是连通的吗
int count() 与 s 连通的顶点总数
}

我们用起点（source）区分作为参数传递给构造函数的顶点与图中的其他顶点。在这份 API 中，构造函数的任务是找到图中与起点连通的其他顶点。
用例可以调用 marked() 方法和 count() 方法来了解图的性质。方法名 marked() 指的是这种基本算法使用的一种实现方式

本章中会一直使用到这种算法：在图中从起点开始沿着路径到达其他顶点并标记每个路过的顶点。

1-4-2.深度优先搜索

我们已经见过 Search API 的一种实现：第 1 章中的 union-find 算法。
它的构造函数会创建一个 UF 对象，对图中的每一条边进行一次 union() 操作并调用 connected(s,v) 来实现 marked(v) 方法。
实现 count() 方法需要一个加权的 UF 实现并扩展它的 API，以便使用 count() 方法返回 wt[find(v)]（请见练习 4.1.8）。

这种实现简单而高效，但下面我们要学习的实现还可以更进一步。它基于的是深度优先搜索（DFS）的。这是一种重要的递归方法，
它会沿着图的边寻找和起点连通的所有顶点。深度优先搜索是本章中将学习的好几种关于图的算法的基础。

1-4-3.深度优先搜索定义

要搜索一幅图，只需用一个递归方法来遍历所有顶点。在访问其中一个顶点时：
1.将它标记为已访问；
2.递归地访问它的所有没有被标记过的邻居顶点。

这种方法称为深度优先搜索（DFS）。Search API 的一种实现使用了这种方法，如深度优先搜索框注所示。
它使用一个 boolean 数组来记录和起点连通的所有顶点。
递归方法会标记给定的顶点并调用自己来访问该顶点的相邻顶点列表中所有没有被标记过的顶点。如果图是连通的，每个邻接链表中的元素都会被检查到。

我们常常通过系统地检查每一个顶点和每一条边来获取图的各种性质。
要得到图的一些简单性质（比如，计算所有顶点的度数）很容易，只要检查每一条边即可（任意顺序）。

但图的许多其他性质和路径有关，因此一种很自然的想法是沿着图的边从一个顶点移动到另一个顶点。尽管存在各种各样的处理策略，
但后面将要学习的几乎所有与图有关的算法都使用了这个简单的抽象模型，其中最简单的就是下面介绍的这种经典的方法。

1-4-4.深度优先搜索 使用场景

这种简单的递归模式只是一个开始——深度优先搜索能够有效处理许多和图有关的任务。

用深度优先搜索来解决在第 1 章首次提到的一个问题。 连通性。给定一幅图，回答“两个给定的顶点是否连通？”或者“图中有多少个连通子图？”等类似问题。

但是，在 1.5 节学习的 union-find 算法的数据结构并不能解决找出这样一条路径的问题。深度优先搜索是我们已经学习过的几种方法中第一个能够解决这个问题的算法。

单点路径。给定一幅图和一个起点 s，回答“从 s 到给定目的顶点 v 是否存在一条路径？如果有，找出这条路径。”等类似问题。
深度优先搜索算法之所以极为简单，是因为它所基于的概念为人所熟知并且非常容易实现。事实上，它是一个既小巧而又强大的算法，研究人员用它解决了无数困难的问题。

1-4-5.寻找路径

单点路径问题在图的处理领域中十分重要。根据标准设计模式，我们将使用如下 API:

public class Paths{
    Paths(Graph G, int s)       在 G 中找出所有起点为 s 的路径
    boolean hasPathTo(int v)    是否存在从 s 到 v 的路径
    Iterable<Integer>pathTo(int v) s 到 v 的路径，如果不存在则返回 null
}

在为起点 s 创建了 Paths 对象后，用例可以调用 pathTo() 实例方法来遍历从 s 到任意和 s 连通的顶点的路径上的所有顶点。