题目描述

给一个有  n  个结点的有向无环图，找到所有从  0  到  n-1  的路径并输出（不要求按顺序）

二维数组的第 i 个数组中的单元都表示有向图中 i 号结点所能到达的下一些结点（译者注：有向图是有方向的，即规定了 a→b 你就不能从 b→a）空就是没有下一个结点了。

示例:
输入: [[1,2], [3], [3], []]
输出: [[0,1,3],[0,2,3]]
解释: 图是这样的:
0--->1
|      |
v     v
2--->3
这有两条路: 0 -> 1 -> 3 和 0 -> 2 -> 3.

提示:

• 结点的数量会在范围 [2, 15] 内。
• 你可以把路径以任意顺序输出，但在路径内的结点的顺序必须保证。

来源：LeetCode

思路

很基础的深度优先搜索题目。记录下当前节点，和当前已走的路径，然后从graph中取出所有可以到达的节点，继续搜索。起始节点设为0，当走到n-1时，即得到一个可行路径，存储到结果中。

解法

/**
 * @param {number[][]} graph
 * @return {number[][]}
 */
const allPathsSourceTarget = graph => {
  const result = [];

  const dfs = (current, path) => {
    if (current === graph.length - 1) {
      result.push(path);
      return;
    }

    graph[current].forEach(node => {
      dfs(node, [...path, node]);
    });
  };

  dfs(0, [0]);

  return result;
};