如何停止广度优先搜索递归函数

我想在到达指定单元格后停止我的广度优先搜索功能。如何停止广度优先搜索递归函数

现在我在到达指定单元格后显示警报，但仍然访问其余节点。您可以看到此行为here（请选择广度优先搜索）。

function drawBreadthFirstSearch(current, start, last, queue, animation_speed) { 
    setTimeout(function() { 
     if (queue.length >= 0) { 
      current = queue.shift(); 

      if (current !== last) { 
       current.color = "#c6e0b4"; 
       current.changeColor(); 
      } else { 
       alert('The end!') 
       return 
      } 

      var childs = checkNeigbors(current.i, current.j) 
      if (childs) { 
       childs.forEach(function (child) { 
        if (child.visited === false) { 
         child.color = "green"; 
         child.changeColor(); 

         queue.push(child) 
         child.visited = true; 
         drawBreadthFirstSearch(current, start, last, queue, animation_speed) 
        } 
       }); 
      } 
     } 
    }, animation_speed); 
}

函数checkNeigbors返回单元格数组。

将forEach更改为for没有帮助。

来源

2017-09-09 Nikita Yunoshev

你有一些失踪'，'。在'结束'行和'返回'后面没有';'。同样在'queue.push（child）'... – Airwavezx

thx，但它不能解决我的问题。 –

这个算法不是广度优先的，而是深度优先的，除此之外（当我谈到javascript时，我不太熟练）看起来像是异步的，当正确的函数被发现很棘手时，这会使中止。 – Paul

它继续的原因是forEach循环将启动几个递归调用，它们都启动一个计时器。所以等待定时器的数量随着搜索树的宽度的增加而增加。并且结束的回调，其中一个定时器不会阻止其他待定时器执行其回调。

一个简单的解决方法是在找到匹配项时尽快将队列清空。由于定时器回调仅在队列不为空时执行某些操作，所以和之间的队列引用会在所有函数调用中共享，您可以通过这种方式避免任何进一步的搜索。

第一，达到理想的电池时，应通知递归有关情况：

 queue.length = 0; // <--- add this. 
     alert('The end!') 
     return

来源

2017-09-09 13:42:00 trincot

谢谢，先生。它有帮助。我明白，为每个启动几个递归调用，但我已经尝试过“队列= []”，并没有帮助） –

'队列= []'没有帮助，因为它只会改变局部变量，然后点到内存中的* new *数组，而不会影响* original *数组的内存位置：它将从原始数组中分离出来，并且其他函数调用仍将查看原始数组。相反，你必须* mutate *所有这些'queue'变量引用的对象，然后他们都会看到变化。 – trincot

，以达到有搜索，你应该在三个地方使用返回值的单元格后停止对子女和兄弟姐妹迭代以发生在搜索结束：

 } else { 
      alert('The end!'); 
      return false; 
     }

第二返回命令应该是在以停止遍历该节点的孩子foreach循环，如果我们已经找到了所需的细胞：

     if (!drawBreadthFirstSearch(current, start, last, queue, animation_speed)) return false;

第三回命令应该是最后一个函数的线，它代表：仍然没有找到小区，继续搜索：

 }, animation_speed); 
     return true; 
    }

来源

2017-09-09 15:05:51 shayuna

如何停止广度优先搜索递归函数

回答

相关问题