算法：有向图深度优先

基本算法

描述：遍历图$G$的所有节点，对每个$v$，递归的访问$v$的所有的没被访问过的子节点。递归的意思是
1. (Recursion)子节点的子节点。
2. (Base Case/boundary condition)当前节点没有子节点了(除了已经被访问过的)。

要维护节点是否被访问过每个节点需要有个标志位，也就是一个长度为$n$的数组。





算法附加给图的结构

首先节点被touch的顺序给出了一个节点的序。

对于边，在算法运行的过程中会遇到两种边，一种是发现指向的子节点被touch过；一种是指向子节点没被touch过。对子节点没被touch过的情况，这个边称为"tree edges"。

对子节点已经被touch过的情况，设$u$是当前节点，$v$是子节点。现在考虑进入访问$u$的这个递归堆栈，$v$可能在进入之前已经被touch过，或者是进入堆栈之后被touch的，现在又遇到了。

对于进入堆栈之后被touch的，$v$必然是$u$的后代，且不是直接后代(直接后代必然是第一次被touch)，这种边称为"forward edges"。

对于进入堆栈之前被touch的，又可以分成两种情况:
1.$u$是在访问$v$的递归堆栈里被访问的，也就是说$u$是$v$的后代，名分已定，这时候我们还在访问$v$的递归堆栈里(其实整个访问$u$的递归堆栈都在访问$v$的递归堆栈里)，这种边称为"back edges"。
2.访问$v$的递归堆栈早已结束，$v$是那时候被touch的，$u$，$v$代表的堆栈没有任何关系，这种边叫"cross edges"。

现在改变程序记录上面提到的节点和边的信息。

touched[n]已经记录了节点是不是被touch过了的信息，现在要增加记录什么时候被touch的，首先我们要记录每个节点的递归堆栈开始和结束的时间，这需要两个长度为n的数组，start[n]，end[n]。每次进入一个节点递归堆栈和出去的时候时间加1。

这两个数组含有的信息包含了touched[n]包含的信息，进入节点的递归堆栈的时候就是节点被touch的时候，当start[i]不为0的时候就是touched[i]不为0的时候，所以touched[i]可以去掉了。

按v的信息(start[v],end[v])来分类:
(0, 0)直接后代:tree edge. (白色)
(0, b)不可能
(a, 0)$\Leftrightarrow$ b = 0, v堆栈还未完成: back edge.(灰色)
(a, b)$\Leftrightarrow$ b != 0, v堆栈已经完成: forward edge(a > start[u])/cross edge(b < start[u]) (黑色) 另一种算法是节点染色，标在括号里了。

对无向图来说上面的第4中情况，遍历u的邻居的时候发现v的堆栈已经完成，说明v到u之间的连接已经考虑过了，只是因为我们使用矩阵表示的原因循环中又出现一遍，可以直接抛弃，所以无向图里没有forward edge/cross edge的说法。