判断graph是否存在环

今天做了一道题目 来源于leetcode上的Course Schedule
这道题是典型的求图中有没有环的问题，这一题我使用的是dfs遍历，在算法引论这本书中，鉴别图中有没有环的办法是判断是否有一条后退边，即从后代链接到子孙的边 那么具体到算法的实现如下
首先根据所给的数组 来构造graph 这里我们使用Map来标记graph

var prerequisites = [[1, 0], [0, 1]]
var graph = new Map ()
/** 构建图的js实现 **/
for (let [v, e] of prerequisites) {
    if (graph.has(v)) { // 如果已经有到v这个定点的边，那么就把新发现的边push到边的数组里
        let edges = graph.get(v)
        edges.push(e)
        graph.set(v, edges)
    } else {
        // 第一次发现顶点的时候 就把边push进数组
        graph.set(v, [e])
    }
}

那么这样我们便完成了图的构建，利用Map 形成了一个键值对，key是v顶点，graph[v]便是键值对 那么接下来就是主动找到环的问题了，首先 我们用一个Set标注已经访问过的边，因为Set中不会有重复的键值
那么接下来的原理也就很简单了，比如我们访问0这个顶点的时候 dfs 这个顶点的边 如果这个顶点有到0的边 那么就可以认为存在一个环
那么重点也就来了 我们需要两个Set
一个是标注是否已经访问了这个顶点的visited
另一个是标注在访问当前访问的顶点visiting
为什么要标注这样两个Set呢

例如 {0: [1,2,3,4] 1: [4]} 0有到4的边，1也有到4的边，但是在dfs 0的时候 就会把4标注为 visited 实际上这里并没有环，那么就用visiting 来标注 算法如下所示

var find_circle = function (v) {
    let edges = graph.get(v)
    visiting.add(v)
    if (edges && edges.length > 0) {
        for (let e of edges) {
            if (visited.has(e)) {
              // 如果已经访问了这个节点 那么就跳出这个循环
                continue
            } else if (visiting.has(e)) {
              // 如果同时也访问了e 表示在遍历v的边时 有一条指向v的后退边
                return true
            } else if (find_circle(e)) {
              // dfs e的顶点时 发现有指向e的后退边
                return true
            }
        }
    }
    // visiting.delete(v)
    visited.add(v) // 标注已经访问过这个节点
    return false
}

然后就是对每个顶点进行遍历

for (let [v, e] of graph) {
  if (find_circle(v)) {
    return false
  }
}