图论基础及遍历算法

797. 所有可能的路径 (opens new window)

/**
 * @param {number[][]} graph
 * @return {number[][]}
 */
var allPathsSourceTarget = function (graph) {
  const res = []
  const path = []
  const n = graph.length
  const traverse = (graph, s) => {
    // 添加路径
    path.push(s)
    // 得到结果
    if (s === n - 1) {
      // js特性 引用传值
      res.push([...path])
    }
    // 多叉树遍历框架
    for (let v of graph[s]) {
      traverse(graph, v)
    }
    path.pop()
  }

  traverse(graph, 0)

  return res
}

::: Tip 判断有环 添加 visible 记录是否已经走过 :::