javascript - Variable not updating in recursive call

Question

I am trying to implement leetcode allpaths problem I have written the below solution, which is giving me the wrong output, I have purposefully, left the console statements for better debugging. Basically the variable path does not gets updated to [0] whenever the recursive call to findPath is done.

What am I missing here?

const allPaths = (edges) => {
  const graph = buildAdjacencyListGraph(edges);
  console.log(graph);
  const result = []
  let path = [0];
  findPath(graph, 0, edges.length - 1, result, path)
}

const findPath = (graph, src, dest, result, path) => {
  for (let neighbor of graph[src]) {
    console.log('Path before push: ', path);
    console.log('Result before push: ', result);
    path.push(neighbor);
    console.log('Path: ', path);
    console.log('Result: ', result);
    console.log('Neighbor', neighbor);
    console.log('Destination: ', dest);
    console.log('Is neighbor and dest equal?: ', dest === neighbor);
    if (neighbor === dest) {
      result.push([...path])
      console.log('Result after equal: ', result);
      path = [0];
      console.log('Path after equal: ', path);
      continue;
    }
    findPath(graph, neighbor, dest, result, path);
  }
}

const buildAdjacencyListGraph = (edges) => {
  const graph = {};

  for (let [i, edge] of edges.entries()) {
    graph[i] = edge;
  }
  return graph;
}
const graph = [[4,3,1],[3,2,4],[3],[4],[]]

allPaths(graph)

标签： javascriptdepth-first-search

Answer 1

有几个问题：

• allPaths没有return声明。它应该以return result.

• result.push([...path])用 重置路径是错误path = [0]的。路径应该只返回到其先前的状态，以便可以从那里探索替代的延续。通过将其设置为[0]，循环的下一次迭代可能会向该路径添加一个节点，该路径根本没有从 0 开始的连接。

• 在进行递归调用之后，路径应该在进行下一次迭代之前返回到其先前的状态，因为我们不希望将当前邻居保留在那里，在其后添加下一个邻居。不，下一个邻居应该替换路径中的当前邻居。

不是真正的问题，但您创建的邻接列表确实是不必要的。你得到的已经是一个邻接列表，它是一个列表列表而不是列表的字典。但是由于键是 0..n-1，所以它确实以相同的方式使用。您可以跳过该转换。

因此，通过这些更正，代码变为：

const allPaths = (edges) => {
  // no need for calling buildAdjacencyListGraph
  const result = [];
  findPath(edges, 0, edges.length - 1, result, []); // no need for path variable
  return result;
}

const findPath = (graph, src, dest, result, path) => {
  for (let neighbor of graph[src]) {
    path.push(neighbor);
    if (neighbor === dest) {
      result.push([...path]);
    } else {
      findPath(graph, neighbor, dest, result, path);
    }
    path.pop(); // backtrack!
  }
}