深度优先遍历判断有向图环路

本质上，就是通过深度优先来完成所有边的遍历，一旦有环必然会被发现。

深度优先遍历这个大家已经很熟悉了，我们需要做的是在每次增加深度时，记下从起点到当前节点所经过的所有节点，一旦重复访问了已经访问过的节点，就必然是有环的。

那么我们就需要用一个数组来记录已经访问过的节点。

又因为路径中的分叉，所以在记录访问状态的时候，必须要考虑到节点复用的问题，即一个节点有多个分叉的问题。节点应该有三个状态才能满足这些要求，即：

[未搜索]：全新节点

[搜索中]：我们搜索过这个节点，但是该节点的所有分支和子分支并没有搜索完

[已完成]：该节点的分支和子分支已经全部搜索完毕，没有环路

到这里，我们的算法也很明显了：

1. 任取一个[未搜索]的节点x开始深度优先搜索，并将该节点标记为[搜索中]
2. 遍历该节点x的每一个相邻节点y；
   • 如果y 是[未搜索]节点，那么从y结点开始深度优先搜索；
   • 如果y是[搜索中]节点，那么代表图中有一个环；
   • 如果y是[已完成]节点，那么代表该节点的分支及子分支已经确认是无环了，不用进行操作；
3. x的所有节点都是[已完成]时，则代表着该图是无环的；