陶尔扬算法

1. DFS的搜索的过程

当节点v的所有边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。
深度优先搜索是一种在开发爬虫早期使用较多的方法。在一个HTML文件中，当一个超链被选择后，被链接的HTML文件将执行深度优先搜索，即在搜索其余的超链结果之前必须先完整地搜索单独的一条链。深度优先搜索沿着HTML文件上的超链走到不能再深入为止，然后返回到某一个HTML文件，再继续选择该HTML文件中的其他超链。当不再有其他超链可选择时，说明搜索已经结束。优点是能遍历一个Web 站点或深层嵌套的文档集合；缺点是因为Web结构相当深,，有可能造成一旦进去，再也出不来的情况发生。
事实上,深度优先搜索属于图算法的一种,英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止,而且每个节点只能访问一次.
深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的相应拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如最大路径问题等等。
因发明“深度优先搜索算法”，霍普克洛夫特与陶尔扬共同获得计算机领域的最高奖：图灵奖.
正如算法名称那样，深度优先搜索所遵循的搜索策略是尽可能“深”地搜索图。在深度优先搜索中，对于最新发现的顶点，如果它还有以此为起点而未探测到的边，就沿此边继续汉下去。当结点v的所有边都己被探寻过，搜索将回溯到发现结点v有那条边的始结点。这一过程一直进行到已发现从源结点可达的所有结点为止。如果还存在未被发现的结点，则选择其中一个作为源结点并重复以上过程，整个进程反复进行直到所有结点都被发现为止。
和宽度优先搜索类似，每当扫描已发现结点u的邻接表从而发现新结点v时，深度优先搜索将置v的先辈域π[v]为u。和宽度优先搜索不同的是，前者的先辈子图形成一棵树，而后者产生的先辈子图可以由几棵树组成，因为搜索可能由多个源顶点开始重复进行。因此深度优先搜索的先辈子图的定义也和宽度优先搜索稍有不同： Gπ=(V,Eπ),Eπ={(π[v],v)∈E:v∈V∧π[v]≠NIL}
深度优先搜索的先辈子图形成一个由数个深度优先树组成的深度优先森林。Eπ中的边称为树枝。
和宽度优先搜索类似，深度优先在搜索过程中也为结点着色以表示结点的状态。每个顶点开始均为白色，搜索中被发现时置为灰色，结束时又被置成黑色(即当其邻接表被完全检索之后)。这一技巧可以保证每一顶点搜索结束时只存在于一棵深度优先树上，因此这些树都是分离的。
除了创建一个深度优先森林外，深度优先搜索同时为每个结点加盖时间戳。每个结点v有两个时间戳：当结点v第一次被发现(并置成灰色)时记录下第一个时间戳d[v]，当结束检查v的邻接表时(并置v为黑色)记录下第二个时间截f[v]。许多图的算法中都用到时间戳，他们对推算深度优先搜索进行情况是很有帮助的。 下列过程DFS记录了何时在变量d[u]中发现结点u以及何时在变量f[u]中完成对结点u的检索。这些时间戳为1到2|V|之间的整数，因为对每一个v中结点都对应一个发现事件和一个完成事件。对每一顶点u，有 d[u]<f[u]
(1) 在时刻d[u]前结点u为白色，在时刻d[u]和f[u]之间为灰色，以后就变为黑色。 下面的伪代码就是一个基本的深度优先搜索算法，输人图G可以是有向图或无向图，变量time是一个全局变量，用于记录时间戳。
procere DFS(G); - begin
- 1 for 每个顶点u∈V[G] do
- begin
- 2 color[u]←White;
- 3 π[u]←NIL;
- end;
- 4 time←0;
- 5 for 每个顶点u∈V[G] do
- 6 if color[u]=White
- 7 then DFS_Visit(G,u);
- end; -
- procere DFS_Visit(G,u);
- begin
- 1 color[u]←Gray; Δ白色结点u已被发现
- 2 d[u]←time←time+1;
- 3 for 每个顶点v∈Adj[u] do Δ探寻边(u,v)
- 4 if color[v]=White
- then begin
- 5 π[v]←u;
- 6 DFS_Visit(G,v);
- end;
- 7 color[u]←Black; Δ完成后置u为黑色
- 8 f[u]←time←time+1;
- end;
- 图2说明了DFS在图1所示的图上执行的过程。被算法探寻到的边要么为阴影覆盖 (如果该边为树枝)，要么成虚线形式 (其他情况)。对于非树枝的边，分别标明B(或F)以表示反向边、交叉边或无向边。我们用发现时刻Z完成时刻的形式对结点加盖时间戳。
图2 深度优先搜索算法DFS在有向图图1上的执行过程
过程DFS执行如下。第1-3行把所有结点置为白色，所有π域初始化为NIL。第4行复位全局变量time，第5-7行依次检索V中的结点，发现白色结点时，调用DFS_Visit去访问该结点。每次通过第7行调用DFS_Visit时，结点u就成为深度优先森林中一棵新树的根，当DFS返回时，每个结点u都对应于一个发现时刻d[u]和一个完成时刻f[u]。 每次开始调用DFS_Visit(u)时结点u为白色，第1行置u为灰色，第2行使全局时间变量增值并存于d[u]中，从而记录下发现时刻d[u]，第3-6行检查和u相邻接的每个顶点v，且若v为白色结点，则递归访问结点v。在第3行语句中考虑到每一个结点v∈Adj[u]时，我们可以说边(u,v)被深度优先搜索探寻。最后当以u为起点的所有边都被探寻后，第7-8行语句置u为黑色并记录下完成时间f[u]。
算法DFS运行时间的复杂性如何？DFS中第1-2行和5-7行的循环占用时间为O(V),这不包括执行调用DFS_Visit过程语句所耗费的时间。事实上对每个顶点v∈V，过程DFS_Visit仅被调用一次，因为DFS_Visit仅适用于白色结点且过程首先进行的就是置结点为灰色，在DFS_Visit(v)执行过程中，第3-6行的循环要执行|Adj[v]|次。因为∑v∈V|Adj[v]| =θ(E)，因此执行过程DFS_Visit中第2-5行语句占用的整个时间应为θ(E)。所以DFS的运行时间为θ(V+E)。

2. 深度优先算法的定义

深度优先搜索算法（Depth-First-Search），是搜索算法的一种。是沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所有边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。
深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的相应拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如最大路径问题等等。
因发明“深度优先搜索算法”，霍普克洛夫特与陶尔扬共同获得计算机领域的最高奖：图灵奖.