【算法概论】图论算法：有向图中环的判断问题_previsit函数

问题描述：

       给定一个有向图，要求使用深度优先搜索策略，判断图中是否存在环。

❗算法分析❗：

       判断图中是否存在环，要涉及到图的拓扑排序。回看数据结构的书?，上面是这样写的：

       基于环性质，在对有向图进行深度优先搜索?中，可以检查图中是否存在环，并进行拓扑排序。为检测图中是否存在反向边，可使用类似二叉树后序遍历的思想。即，在深度优先搜索中，对当前被访问的任一顶点 v 做访问标记，但不立即输出，而是将输出推迟到它的所有可达顶点（后继顶点）被输出之后。为了保证输出的顶点序列具有拓扑顺序，输出时应将顶点 v 插在它的所有后继顶点之前。这样，在深度优先搜索过程中每个顶点有 未被访问、已访问、已输出 三种状态。对任一顶点 v ，初始状态为 未被访问。当一个顶点被访问后，其状态由 未被访问 变为 已访问，接着检查它的每一个邻接点的状态。若某个邻接点的状态为 已访问，则表明图中有环。

       1、关于邻接表表示法中的拓扑排序问题，在【数据结构】图 - 邻接表表示法 这篇中，已经复习过。

       2、同时，在上述一段话中，还提到了DFS时顶点的三种状态：

       vis 标记 一个顶点的访问情况。

       vis = 0，表示该顶点没没有被访问；
       vis = 1，表示该顶点已经被访问，但其子孙后代还没被访问完 —— 还没从该点返回；
       vis = 2，表示该顶点已经被访问，其子孙后代也已经访问完 —— 已经从该顶点返回。

       3、上面一段话提到一个概念 —— 反向边，❀ 这就跟上课的内容有点联系啦 ?

       上课时，有几个概念：树边、前向边、回边、横跨边，从定义可以看出，这几个概念是图进行DFS时才有的概念。

       进行概念阐述时，让我们与顶点的三种状态结合起来。

       DFS过程中，对于一条边 u → v，

       vis[v] = 0，v 是 首次发现，边 u → v是树边；

       vis[v] = 1，说明 v 已经被访问，但其子孙后代还没有被访问完（正在访问中），而 u 又指向 v，说明 u 就是 v 的子孙后代，