797.所有可能的路径

链接：797.所有可能的路径
难度：Medium
标签：深度优先搜索、广度优先搜索、图、回溯
简介：给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出。

题解 1 - typescript

• 编辑时间：2021-08-25
• 执行用时：136ms
• 内存消耗：45.4MB
• 编程语言：typescript
• 解法介绍：dfs。

class GNode {
  prev: GNode[] = [];
  next: GNode[] = [];
  constructor(public val: number) {}
}
function allPathsSourceTarget(graph: number[][]): number[][] {
  const n = graph.length;
  const list: GNode[] = new Array(n);
  for (let i = 0; i < n; i++) {
    let node = list[i];
    if (!node) list[i] = node = new GNode(i);
    const nextList = graph[i];
    for (const next of nextList) {
      let nextNode = list[next];
      if (!nextNode) list[next] = nextNode = new GNode(next);
      node.next.push(nextNode);
      nextNode.prev.push(node);
    }
  }
  const ans: number[][] = [];
  dfs(list[0]);
  return ans;
  function dfs(node: GNode, list: GNode[] = []) {
    list.push(node);
    if (node.val === n - 1) ans.push(list.map(v => v.val));
    if (node.next.length !== 0) node.next.forEach(v => dfs(v, list));
    list.pop();
  }
}

题解 2 - typescript

• 编辑时间：2021-08-25
• 执行用时：160ms
• 内存消耗：49MB
• 编程语言：typescript
• 解法介绍：dfs。

function allPathsSourceTarget(graph: number[][]): number[][] {
  const n = graph.length;
  const ans: number[][] = [];
  dfs(0);
  return ans;
  function dfs(node: number, list: number[] = []) {
    list.push(node);
    if (node === n - 1) ans.push(list.slice());
    graph[node].forEach(v => dfs(v, list));
    list.pop();
  }
}