javascript - 为什么在执行递归回调时 .foreach 的行为与 for...of 不同?
问题描述
我正在使用邻接表编写递归深度优先图遍历,邻接表是一个包含顶点作为键的对象,每个键的邻居作为值的数组。递归调用辅助函数来访问初始顶点的所有邻居,然后访问这些邻居的所有邻居,等等。
出于某种原因,使用“for...of”循环遍历每个相邻数组无法正常工作。将在邻居的邻居的邻居上调用辅助函数,但是当达到基本情况时,辅助函数似乎不会在初始邻居的其他邻居上调用,因此您最终会死-永远无法达到的目的。
function depthFirstRecursiveTraversal(initialVertex) {
const adjacencyList = {
A: ['B', 'C'],
B: ['A', 'D'],
C: ['A', 'E'],
D: ['B', 'E', 'F'],
E: ['C', 'D', 'F'],
F: ['D', 'E']
};
let visited = {};
let vertexList = [];
function dfsHelper(v) {
if (!v) return null;
vertexList.push(v);
visited[v] = true;
// Why does a for-of loop fail here? Recursion fails to reach all vertices
//for (const neighbor of adjacencyList[v]) {
// if (!visited[neighbor]) return dfsHelper(neighbor);
//}
// But using forEach instead works!
adjacencyList[v].forEach(neighbor => {
if (!visited[neighbor]) return dfsHelper(neighbor);
});
}
dfsHelper(initialVertex);
return vertexList;
}
调用 depthFirstRecursiveTraversal(A) 返回 [ 'A', 'B', 'D', 'E', 'C', 'F' ],这是正确的。
但是如果你注释掉 forEach 并在 for...of 循环中注释,它会返回 ['A', 'B', 'D', 'E', 'C' ] - 'F' 顶点永远不会到达。
作为参考,这就是图表的样子:
A
/ \
B C
| |
D --- E
\ /
F
谁能告诉我为什么 for...of 失败,但 foreach 有效?
解决方案
在for
循环内部,return
将终止整个dfsHelper
函数。相反,在forEach
回调内部,return
只是终止回调。
返回值在这里无关紧要,返回除了引入这个错误之外没有任何作用。最好return
从两个版本中删除 - 如果你这样做,for..of
工作正常:
function depthFirstRecursiveTraversal(initialVertex) {
const adjacencyList = {
A: ['B', 'C'],
B: ['A', 'D'],
C: ['A', 'E'],
D: ['B', 'E', 'F'],
E: ['C', 'D', 'F'],
F: ['D', 'E']
};
let visited = {};
let vertexList = [];
function dfsHelper(v) {
if (!v) return null;
vertexList.push(v);
visited[v] = true;
for (const neighbor of adjacencyList[v]) {
if (!visited[neighbor]) dfsHelper(neighbor);
}
}
dfsHelper(initialVertex);
return vertexList;
}
console.log(depthFirstRecursiveTraversal('A'));
推荐阅读
- javascript - 如何使 k-means 算法起作用
- ssas - SSAS MDX 上一年 - 国家/地区聚合问题
- jekyll - 在 Liquid 标签调用中使用变量而不是字符串
- excel - Insert before Table 在文档开头输入文本
- c++ - Qt:在 connect(...) 中使用函子作为发送者
- jenkins - Jenkinsfile/Groovy:尝试在另一个类中使用枚举时无法解析符号 [...] 错误
- c++ - 通用 C++ 回调映射,有没有更好的方法?
- amazon-web-services - CloudFormation 不适合创建 SSM 文档吗?
- java - Flutter 需要更新版本的 Android SDK。要更新,请运行:错误?
- java - 有没有办法在 Spark 的单个计算中编写两个数据集输出