前言
看了看本文的篇幅，我才发现自己对深度优先搜索的理解只停留在概念上，没有太深入去思考它的用处在哪里。接下来跟着jeff教授的讲解，来了解深度优先搜索在有向图中的应用吧。
知识点
上一章我们讨论过一个任意图遍历的通用算法（任意优先搜索）。这一章，我们重点讲解这个算法的一个实例—深度优先搜索，并且主要针对有向图。
尽管深度优先搜索可以被准确表述为“使用栈的任意优先搜索”，但是这个算法通常是递归实现的，并没有显式使用到栈。
如果我们对已经访问过的节点进行标记，可以让这个算法执行的快一点。这个改动保证了对每个顶点v只执行一次DFS(v)。通过引入两个黑盒子子程序，PreVisit和PostVisit，我们可以计算出一些关于顶点和边的有用信息。
回忆一下在有向图G中一个节点v可以到达另一个节点w—或者更简单的说，v可以到达w—当且仅当G包含了一条从v到w的有向路径。用reach(v)表示一个可以从v到到达的顶点集合（包含v本身）。如果我们清除G中所有顶点的标记，然后调用DFS(v)遍历v所在的连通分量，完成之后标记的所有顶点恰恰就是reach(v)。
可达性在无向图中是对称的：v可以到达w当且仅当w可以到达v。标记了一个无向图G中的所有顶点后，调用DFS(v)遍历的是v所在的连通分量，这些父指针正好定义了当前连通分量的生成树。
这种情况在有向图中更复杂一些，由下图可见。即使图是连通的，不同的顶点可以到达不同的或者可能重复的区域。DFS(v)指定的父指针定义了一棵以v为根节点的数，它的顶点恰恰是reach(v)，但是就没必要去讨论这个图的生成树了。
照例，我们可以扩展可达性算法来遍历整个输入图，即使它是不连通的，使用下图所示标准的包装函数。这里我们增加一个通用的黑盒子子程序Preprocess来执行一些PreVisit和PostVisit函数的必要的初始化。
或者，如果允许修改原图，我们可以增加一个源顶点s，和从s到G中每一个其他顶点的边，然后只需要调用DFS(s)即可，如上图的右边部分所示。从本质上来说两个包装函数是相同的；哪个方便就用哪个。
此外，这个算法对于有向图和无向图有些微不同。在无向图中，正如我们上一章所见，采用DFSAll来计算图中的连通分量个数是很轻松的；特别是DFSAll计算出的父指针定义了一片输入图的连通森林，它包含了每个连通分量的生成树。当这个图是有向的，DFSAll找到“连通分量”的数量会在1到V之间，即使这个图是“连通的”，具体情况取决于图所采用的数据结构和包装函数中访问顶点的顺序。
前序和后序
希望你已经了解过有根树的前序和后序遍历，两种方式都可以用深度优先搜索来计算。类似地，即使图是不连通的，关于任意有向图的遍历顺序可以通过分发一个计数如下图所示定义。同样地，我们可以使用带有下面子程序Preprocess，PreVisit，PostVisit的通用深度优先搜索算法。
这个算法会刚好在v推进递归栈之后为v.pre分配值（同时colck的值增加），并且也会刚好在v弹出递归栈之后为v.post分配值（同时colck的值增加）。这表示对于任意两个顶点u和v，[u.pre,u.post]和[v.pre,v.post]的区间段不是嵌套的就是不相交的。而且，[u.pre,u.post]包含[v.pre,v.post]区间，当且仅当DFS(v)在DFS(u)的执行过程中被调用或者说u是v在最终森林中的父指针中的一个祖先。
在DFSAll标记了图中的每个节点后，v.pre记录了所有顶点的前序序列，v.post记录了所有顶点的后序序列。通过一些特殊例子，我们发现每个图都有集合不同的前序和后续序列，这取决于DFS离开每个顶点时选择边的顺序以及DFSAll遍历顶点的顺序。
这个章节的余下部分，我们使用v.pre来作为v的起始时间，v.post作为v的结束时间，起始和结束之间的这段时间作为v的活跃区间。
顶点和边分类
在整个DFSAll的执行过程中，输入图中的每个顶点都会处于下面三个阶段之一：
• 未使用：DFS(v)还没有没被调用，clock < v.pre；
• 活跃：DFS(v)已经被调用但是还没有返回，v.pre ≤ clock ＜ v.post;
• 完成：DFS(v)已经返回，v.post ≤ clock。
因为起始和结束的时间对应着递归栈的推进和弹出，一个点是活跃的当且仅当它在递归栈中。这表示这些活跃的节点总是能组成G中的一个有向路径。
输入图中的边可以划分为四个种类，这取决于他们的活跃区间的交叠情况。假设有一条边u→v。
•如果v在DFS(u)开始时是未使用的，那么DFS(v)一定会在DFS(u)的执行期间被调用，不是直接的就是通过一些中间的递归调用。在任意一种情况下，u都是v在深度优先森林中的祖先，u.pre < v.pre < v.post < u.post。
- 如果DFS(u)直接调用DFS(v)，那么u = v.parent 并且u→v被称为树边。
- 否则，u→v会被称为前向边。
•如果v在DFS(u)开始时是活跃的，那么v早就已经在递归栈里面了，这表示一个相反的嵌套关系v.pre < u.pre < u.post < v.post。此外，G一定包含了一条从v到u的有向路径。满足这个条件的边被称为后向边。
•如果v在DFS(u)开始时是完成的，我们马上得到v.post < u.pre。满足这个条件的边被称为交叉边。
•最后，第四种情况u.post < v.pre是不可能的。
这些边的种类可在下图中看见，实际上边的分类取决于DFSAll遍历顶点的顺序以及DFS在离开每个顶点时选择边的顺序。
最后，下面这个关键的引理描述了根据顶点状态在任意深度优先森林的遍历中祖先和后代。
引理6.1. 已知任何有向图G的一个任意深度优先遍历，下面的陈述对于G中的所有顶点u和v都是等价的。
(a)u是v在深度优先森林中的一个祖先。
(b)u.pre ≤ v.pre < v.post ≤ u.post。
(c)当DFS(v)被调用是，u是活跃的。
(d)在DFS(u)被调用之前，有一条从u到v的路径，其中所有的顶点（包含u和v）都是未使用的。
证明： 首先，假设u是v在深度优先森林中的一个祖先。那么根据定义，存在一条从u到v的树边路径P。通过在路径长度上的归纳，我们得到对于每个在P中的顶点w都有u.pre ≤ w.pre < w.post ≤ u.post，这样每个在P中的顶点在DFS(u)被调用前都是未使用的。特别是，我们得到了u.pre ≤ v.pre < v.post ≤ u.post，这表示u在DFS(v)执行时已经是活跃的了。
因为父指针对应着递归调用，u.pre ≤ v.pre < v.post ≤ u.post说明u是v的一个祖先。
假设u在DFS(v)被调用是是活跃的。那么u.pre ≤ v.pre < v.post ≤ u.post，这表明有一条从u出发的树边路径，通过递归栈中的中间节点到达v。
最后，假设u不是v的祖先。已知任意从u到v的路径P，用x表示P中第一个不是u的后代的顶点，用w表示x在P中的前驱顶点。边w→x保证了x.pre < w.post，又因为w是u的后代，w.post < u.post，所以x.pre < u.post。又因为x不是u的后代，x.pre < u.pre。因为活跃区间应该是正确嵌套的，这里只有两种可能性：
• 如果u.post < x.post，那么x在DFS(u)被调用时是活跃的。
• 如果x.post < u.pre，那么x在DFS(u)被调用时是完成的。
我们得出每一条从u到v的路径都包含了一个顶点在DFS(u)被调用时不是未使用的。
检测环路
一个有向无环图是一个不存在环路的有向图。在有向无环图中入度为0的顶点被称为源点（source）；没有出度的点被称为沉点（sink）。一个孤立无边的顶点即是源点也是沉点。每个有向无环图至少有一个源点和一个沉点，也可以超过一个。比如，一个有n个顶点却没有边的图，每个顶点即是源点也是沉点。
回想一下我们早期分析的一种情况如果对于一条边u→v有u.post < v.post，这个图有一条从v到u的路径，因此它包含了一个通过u→v的有向环路。这样，通过计算顶点的后序序列然后暴力检测每条边，我们可以在O(V+E)时间内确定一个有向图是否无环。
要是不对顶点计数，我们可以维护一个顶点的实时状态，如果我们发现一条到达活跃顶点的边就返回false。这个算法的运行时也是O(V+E)；如下图所示。
拓扑排序
有向图的拓扑序列就是将所有的顶点排在一条水平线上，所有的边都是从左向右的。如果这个有向图是有环的，那么它不可能存在拓扑序列—因为这个环最右侧的顶点会有一条边指向左边！
另一方面，仔细想一下任意有向图的任意一个后序序列。我们早期的分析得到对于每一条边u→v如果u.post < v.post，那么G包含了一条从v到u的有向路径，因此它包含了一个通过边u→v的环路。同样的，如果G是无环的，那么对于每条边u→v都有u.post > v.post。也就是说每个有向无环图G都有一个拓扑序列；尤其是，G的任意逆向后序序列都是G的一个拓扑序列。
如果我们要求将拓扑序列存在一个单独的数据结构中，我们只需要简单地将顶点以逆向后序序列存进数组即可，时间复杂度为O(V+E)。具体改动如下：
隐式拓扑排序
但是将拓扑排序存进单独的数据结构有些小题大做了。在大多数拓扑排序的应用中，顶点的序列表并不是我们的实际目标；相反，我们只是想要对图中的每个顶点执行一些固定的计算，可以用拓扑排序顺序也可以用逆向拓扑顺序。对于这些应用，记录拓扑顺序一点都不重要！
如果我们想要用逆向拓扑顺序处理一个有向无环图，那只要在递归深搜方法的末尾对每个顶点进行处理就足够了。毕竟，拓扑顺序和逆向后序顺序是一样的！
如果我们已经知道输入图是无环的，我们通过标记顶点而不是记录它们的搜索状态来进一步优化这个算法。
这就是一个标准的深度优先搜索算法，只是将子程序PostVisit改为了Process！。
因为这是一个有无环图非常常规的操作，我有时候会将有向无环图的后序处理变为了如下形式：
比如，前面我们隐式的拓扑排序算法可以写成如下形式：
为了以正向拓扑顺序处理有向无环图，我们可以将顶点的拓扑序列存进一个数组然后跑一个简单的for循环。或者，我们可以对G的逆转图（reversal）做深度优先搜索，标记为rev(G)，通过将每一条边v→w变成w→v获得。逆转一个有向图会得到一个相反方向的有向图，所以有向无环图的逆转图还是有向无环的。每一个G中的源点变成了rev(G)中的沉点，并且反之亦然；有归纳可知每个rev(G)的拓扑序列就是G的逆向拓扑序列。任意有向图（使用标准邻接表）的逆转可以在O(V+E)时间内完成。
记忆化和动态规划
我们的拓扑排序算法可以说大概就是广泛类型动态规划算法。回想一下递推式的依赖图对于每个递归子问题都有一个顶点而且一个子问题到另一个都有一条边，如要计算第一个子问题，那么必须要先计算出第二个。这个依赖图必须是无环的，否则单纯的递归算法将不会停止。
记忆化的计算任意递推式其实就和执行依赖图的深度优先搜索是一样的。特别是，一个顶点对应的子问题已经被解决，那么这个依赖图中的顶点就会被标记。黑盒子子程序PreVisit和PostVisit实际上就是真实计算的代理。详见下图：
如果将这个类比继续下去，使用动态规划计算递推式和在依赖图中以逆向拓扑顺序计算所有子问题是一样的—每个子问题的计算时机都是在它的子问题被解决之后。这样，每个动态规划算法和其对应的依赖图的后序遍历是等价的！
然而，大多数动态规划算法和拓扑排序有些细微的不同点。第一，在大多数动态规划算法中，依赖图都是隐式的—节点和边并没有显示地存储，但却编码在所依赖的递推式中。但是这个不同点却是不重要；只要我们可以枚举在常数时间内枚举子问题，我们依然可以当做在遍历存储在邻接表中的依赖图。
更重要的是，大多数动态规划递推式都有高度结构化的依赖图。比如，我们在第五章套路的编辑距离的依赖图就是一个有对角线的常规网格，最佳二叉搜索树的依赖图就是一个所有边都是向上和向右的上三角网格。这种常规的数据结构允许我们将一个合适的计算顺序直接写进算法，特别是一些嵌套循环的集合，所以没有必要在运行中对依赖图拓扑排序。我们提前把逆向拓扑顺序叫做计算顺序。
有向无环图中的动态规划
相反的，我们可以使用深度优先搜索来构造一个结构简单的依赖图问题的动态规划算法。例如，考虑一下最长路径问题，他要求我们在带权边的有向图G中找到一条从一个节点s到另一个节点t权值最大的路径。在常规的有向图中，最长路径是一个NP-hard问题（这个在第十二章有讲），但是如果输入图是无环的就很简单了，我们可以在线性时间内计算出最长路径。
已知目标顶点t，对于任意节点v用LLP(v)表示G中从v到t的最长路径的长度。如果G是一个有向无环图，这个函数满足以下递推式
l(v→w)表示边v→w的权值，max∅=-∞。特别是，如果v是一个不同于t的沉点，那么LLP(v)=-∞。
这个递推式的依赖图就是输入图G本身：子问题LLP(v)取决于子问题LLP(w)当且仅当v→w是一条G中的边。这样，我们可以通过执行一个从s开始对G的深度优先搜索在O(V+E)时间内计算出这个递归函数。这个算法在一个额外的存储区域记录了节点v所对应的长度LLP(v)。
原则上，我们可以将这个记忆化的递归算法转化成一个拓扑排序的动态规划算法：
这两个算法几乎是相同的—第一个算法中的递归和第二个算法中的for循环都代表了同样的深度优先搜索！两个方式任取其一，哪个方便用哪个。
几乎关于最佳决策序列的任何动态规划问题都可以改造成在一个独立的有向无环图中寻找一条最佳路径。比如，文本分割，子集和，最长递增子序列，编辑距离这些在2、3章中的问题都可以重述为在有向无环图中寻找一条最长或最短路径，带权的可能是边也可能是顶点。在各个情况下，问题中的有向无环图就是对应递推式的依赖图。另外，树形动态规划问题，比如寻找最佳二叉搜索树或者树的最大独立集，就不能重述为寻找有向无环图中的最佳路径。
强连通性
让我们回到有向图连通性的正确定义上。回想一下一个有向图G如果包含一条从u到v的路径，那么顶点u可以到达另一个顶点v，reach(u)表示u可以到达的顶点的集合。如果u可以到v，去也可以到达u，那么u和v是强连通的。一个有向图是强连通的当且仅当每对顶点都是强连通的。
有向图的强连通性和无向图的连通性一样的。同样的性质在有向图G中叫做强连通分量。同样地，G的强连通分量就是G中的一个最大强连通子图。一个有向图G是强连通的当且仅当G只有一个强连通分量；有一种极端情况，G是一个有向无环图当且仅当G中的每个前连通分量都是单独的顶点。
强连通分量图scc(G)（也可以称作G的元图）是通过将强连通分量压缩成一个点和把平行边折叠后从G中获得的另一个有向图。证明scc(G)是一个有向无环图并不困难。这样，至少在原则上，可以对G的强连通分量图拓扑排序；这些点可以被排序，所以所有两条边和它们之间的后向边都在同一个强连通分量中。
计算顶点v所在的强连通分量需要O(V+E)的时间。首先我们通过深度优先搜索计算出reach(v)。然后我们通过搜索G的逆转图计算出$reach^{-1}(v)=\{u | v\in reach(u)\}$。最后，v的强连通分量就是$reach(v)\cap reach^{-1}(v)$的相交部分。特别是，我们可以在O(V+E)时间内确定整个图是否强连通。
同样地，我们可以通过将前面的算法和包装函数结合起来计算出一个有向图的所有强连通分量。然而，最终的算法运行时是O(VE)；最多会有V的强连通分量，即便图是无环的每个强连通分量都需要O(E)的时间来确定。当然我们可以做得更好！毕竟，我们在O(V+E)时间内就可以确定每个强连通分量是否为单独的顶点。
线性时间内计算强连通分量
事实上，有好几个算法可以在O(V+E)时间内计算出所有的强连通分量，它们都依赖与下面的观察。
引理6.2. 已知任意有向图G的一个深度优先遍历。G中的每个强连通分量C包含了恰好一个父节点不在C中的节点。（这个节点的父节点可能在别的强连通分量，也可能它没有父节点）
证明： 让C表示G中任意一个强连通分量。假设任意一条从顶点v∈C到另一个顶点w∈C的路径。每一个在这条路径上的顶点都可以到达w，也可以到达C中的每个顶点；对称地，这条路径上的每个顶点都可以从v到达，也可以被每个C中的顶点到达。我们得出每个在这条路径上的点都在C中。
用v作为C中起始时间最早的顶点。如果v有父节点，那么parent(v)在v之前就开始了，而且不可能在C中。
现在用w表示C中的另一个顶点。在DFS(v)被调用之前，所有C中的顶点都是未使用的，所以存在一条从未使用顶点v到顶点w的路径。由引理6.1可知w是v在深度优先搜索森林中的后代。每个在v到w的树边路径上的点都在C中；特别是，parent(w)∈C。
前面这个引理说明有向图G的每个强连通分量定义了G的深度优先搜索森林中的一棵连通子树。尤其是，对于任意强连通分量C，C中起始时间最早的顶点是所有C中顶点最小的共同祖先；我们把这个顶点叫做C的根。
我会给出两个算法，它们都遵循同样的直觉结构。用C表示G中的任意强连通分量，它在scc(G)中是一个沉点；我们把C称作沉分量（sink component）。等价地，如果C中的顶点只能到达C中的顶点，那么C就是一个沉分量。通过重复寻找沉分量中的顶点v，同时找到v能够到达的顶点，然后将这个沉分量从输入图中移除，直到没有顶点剩余。这样我们可以找到G中的所有强连通分量。这还不是一个算法，因为还没有搞清楚怎么去找到沉分量中的一个顶点。
Kosaraju-Sharir算法
咋眼一看，快速找到沉分量中的一个顶点似乎很困难。然而，实际上找到一个源分量中的顶点确很简单—一个G中的强连通分量对应着scc(G)中的一个源点—使用深度优先搜索。
引理6.3. G的后序序列中的最后一个顶点正好是G的源分量中的一个顶点。
证明： 已知G的一个深度优先遍历，用v表示后序序列中的最后一个顶点。那么DFS(v)一定是在包装函数DFSAll中最后被直接调用的。此外，v是深度优先搜索森林中一棵树的根节点，所以任意节点x，x.post > v.pre，都是v的后代。最后，v是它所在强连通分量C的根。
为了方便讨论，假设有一条边x→y，x∉C，y∈C。x可以到达y，y可以到达v，所以x可以到达v。因为v是C的根，顶点y是v的后代，那么v.pre < y.pre。边x→y保证了y.pre < x.post，因此v.pre < x.post。这表示x是v的后代。但是也就是说v可以通过树边到达x，明显这与我们的假设x∉C相矛盾。这说明不存在C之外的顶点可以到达C，那么C一定是一个沉分量。
对于任意有向图G检验rev(scc(G))=scc(rev(G))是比较简单的。这样，rev(G)的后序序列中的最后一个顶点正好是原图G的沉分量中的一个顶点。如此，要是我们再次遍历这个图，这次的包装函数使用rev(G)的逆向后序序列，那么每次调用DFS正好访问G中的一个强连通分量。
把所有东西放到一起，我们得到了上图的算法，它可以在O(V+E)时间内计算和标记出强连通分量。这个算法在1978年被Rao Kosaraju发明（但是未发布），后来在1981年又被Micha Sharir再次独立发明。Kosaraju-Sharir算法有两个阶段，第一个阶段执行rev(G)的深度优先搜索，在它完成之后将每个顶点都推进栈。第二个阶段，我们执行一个原图G的任意优先搜索，按顺序处理栈顶的顶点。这个算法为每个顶点标记了自己所强连通分量的根（在第二次深度优先遍历的时候）。
上图显示了我们的示例图使用Kosaraju-Sharir算法的执行过程。只需要一点点改动，我们也可以在O(V+E)时间内计算出强连通分量图scc(G)。
Tarjan算法
一个更早但是思路更巧妙的计算强连通分量的线性算法在1972年被Bob Tarjan提出。直观上来看，Tarjan算法鉴定出G的源分量，删除它，然后递归的查找剩下的强连通分量；然而，整个计算过程只发生在一次深度优先搜索。
已知某个有向图G的一个任意深度优先遍历。对于每个顶点v，用low(v)表示在所有通过一条伴随最多一个非树边的树边路径可以从v到达的顶点中的最小起始时间。繁琐地，low(v) ≤ v.pre，因为v可以到达本身通过0条非树边和0条树边到达自身。Tarjan对沉分量的观察可以用low函数的形式来描述。
引理6.4. 一个顶点v是G中一个沉分量的根当且仅当low(v) = v.pre且对于每个v的后代w有low(w) ＜ w.pre。
证明： 首先，用v表示一个low(v) = v.pre的顶点。如果w是v的后代，x.pre < v.pre，那么w→x这种边是不存在的。另外，v不能到达任意顶点y，y.pre > v.post。这表明v只能到达它的后代，因此v的后代也只能到达v的后代。特别是，v不能到达它的父节点（如果有的话），所以v是一个强连通分量的根。
现在假设对于每个对于每个v的后代w有low(w) < w.pre。那么每个后代w都能到达另一个顶点x（它必须是另一个v的后代）且x.pre < w.pre。这样，由归纳可知每个v的后代都能达到v。这表明v的后代组成了一个根为v的强连通分量。此外，C一定是一个沉分量，因为v不能到达C以外的顶点。
另外，假设v是沉分量C的根。那么v可以到达另一个顶点w当且仅当w∈C。但是v可以到达所有它的后代，每个C中的顶点都是v的后代，所以v的后代组成了C。如果对于任意别的节点w∈C有low(w) = w.pre，那么w就是C的另一个根，这明显是不可能的。
使用任意深度优先搜索直接计算每个顶点的low(v)；见下图。
由引理6.4可知在运行FindLow之后，我们可以在O(V+E)时间内确定每一个沉分量（通过一个全局的任意优先搜索），然后在O(V+E)时间内标记和删除这些沉分量（通过对每个根调用任意优先搜索），接着继续递归。不幸的是，这个最终算法也许需要执行V次迭代，每次只移除一个点，总运行时为O(VE)。
为了加速这个策略，Tarjan的算法维护了一个顶点的辅助栈（不同于递归栈）。当我们启动一个未使用顶点v时，就把它放到这个栈里面。当我们顶点v状态变为完成时，我们比较v.low和v.pre。然后当我们第一次发现v.low=v.pre时，我们就知道了三件事情：
• 顶点v是沉分量C的根。
• 所有C中的顶点都连续出现在辅助栈的顶部。
• C中的顶点在辅助栈位置最深的是v。
到这里，我们可以通过一个一个弹出辅助栈中顶点直到弹出v来确定C中的顶点。
我们可以删除C中的顶点后继续递归计算剩余图中的强连通分量，但是这样是很浪费的，因为在访问v之前我们将会重复所有的计算。相反，我们标记C中的每个顶点，确定v作为它强连通分量的根，然后对剩余的深度优先搜索忽略标记过顶点。正式地，这个改动将low(v)的定义变为了和v在同一强连通分量中v可以通过伴随最多一条非树边的树边路径到达的顶点中的最小起始时间。但是为了证明正确性，你可以观察忽略标记顶点和实际去删除它们引导的算法行为是一样的。
最后，改动图6.18中的红色加粗部分后，Tarjan算法就是上图所示了。这个算法的运行时可以划分为两部分。每个顶点推进S一次和弹出S一次，所以维护辅助栈的时间是O(V)。如果我们忽略辅助栈的维护，算法的剩下部分就是一个标准的深度优先搜索。我们得出这个算法的运行时为O(V+E)。
结语
没想到深度优先搜索加上前序和后序序列可以推导出这么些顶点和边的重要性质。最让我感到惊喜的还是拓扑序列和动态规划如此密切的关系，这种新旧知识点的融会贯通总能令人印象深刻。至于两个有向图的强连通分量算法，一个比一个设计的巧妙，不过我听得最多的还是Tarjan算法。
原文链接
http://jeffe.cs.illinois.edu/teaching/algorithms/book/06-dfs.pdf