遍历对象时如何停止变量覆盖

Question

所以我正在尝试实现一个简单的 BFS 搜索来解决迷宫问题。我正在使用的代码顶部有一个 test_graph 。当我遍历这段代码时：

        for (var neighbour in graph[vertex])
        {
            console.log("neighbour :", neighbour);
            console.log("path :", path)
            
            let new_path = path;
            new_path.push(neighbour);

            console.log("new path :", new_path);
        }

我得到输出：

neighbour : A
bfs.js:38 path : ["start"]
bfs.js:43 new path : (2) ["start", "A"]
bfs.js:37 neighbour : B
bfs.js:38 path : (2) ["start", "A"]
bfs.js:43 new path : (3) ["start", "A", "B"])

但是，我希望 new_path 的第二次迭代是 ["start", "B"] 而不是 ["start", "A", "B"]。我想将每个邻居（A 和 B）附加到“开始”以创建数组 ["start", "A"] 和 ["start", "B"] 并将其推入队列。

完整代码如下：

const test_graph = {
    start: {A: 1, B: 1},
    A: {C: 1, D: 1},
    B: {A: 1, D: 1},
    C: {D: 1, finish: 1},
    D: {finish: 1},
    finish: {}
};

// Breadth-first search
const BFS = (graph, start, fin) => {
    var queue = [];
    queue.push([start]);
    var visited = [];

    while (Array.isArray(queue) && queue.length)
    {
        // get first path on queue
        var path;
        path = queue.shift();
        //console.log(path); // ["start"]
        
        // get the last node in the path
        var vertex = path[path.length - 1];
        //console.log(vertex); // start
        
        // if end
        if (vertex == fin)
        {
            return path;
        }
        else if (!visited.includes(vertex))
        {
            // for all adjvant nodes, construct new path and push into queue
            for (var neighbour in graph[vertex])
            {
                console.log("neighbour :", neighbour);
                console.log("path :", path)
                
                let new_path = path;
                new_path.push(neighbour);
                queue.push(new_path);    
                console.log("new path :", new_path);
            }
        }
        return;
    }
}

（return就是为了解决这个问题）

Answer 1

let new_path = path; 创建 path 的别名，推送到它（与直接推送到 path 相同），然后在打印后丢弃块末尾的别名。这意味着您一直在使用相同的 path 数组。

最有可能的是，您希望 queue.push(path.concat(neighbour)) 分配一个新数组，连接新的 neighbour 顶点并将其推入队列，有效地将当前路径扩展一个节点但不修改它像 push 那样放置。

除此之外，所有值为 1 的对象似乎有点像邻接表的反模式。 Set 或数组在这里似乎更直观，所以我冒昧地进行了调整以及其他一些调整。

visited 是一个数组意味着查找的复杂度是 O(n)。使用 Set 可以进行 O(1) 次查找，并且是像这样的成员资格测试的正确结构。事实上，visited 在原始版本中是一个未使用的变量，因此如果图形有一个循环，我们将得到一个无限循环。

Array.isArray(queue) 是不必要的检查--queue 纯粹是本地的，如果我们使它 const.

我们不能重新分配它

最后，当 vertex 不在图表中时，通过将 null 合并为空数组来避免崩溃来处理它是个不错的主意（您可能希望输入始终格式正确，但它一个非常简单的调整）。

代码如下：

const shortestPathBFS = (graph, start, destination) => {
  const queue = [[start]];
  const visited = new Set();

  while (queue.length) {
    const path = queue.shift();
    const vertex = path[path.length-1];

    if (vertex === destination) {
      return path;
    } 
    else if (!visited.has(vertex)) {
      visited.add(vertex);

      for (const neighbour of (graph[vertex] || [])) {
        queue.push(path.concat(neighbour));
      }
    }
  }
}

const G = {
  start: [..."AB"],
  A: [..."CD"],
  B: [..."AD"],
  C: ["D", "finish"],
  D: ["finish"],
  finish: [],
};
console.log(shortestPathBFS(G, "start", "finish"));

遍历对象时如何停止变量覆盖

How to stop variable over writing when iterating through object

javascript

arrays

loops

object

breadth-first-search