本文详细解析JavaScript中深度优先搜索（DFS）与广度优先搜索（BFS）的实现原理。通过九宫格路径示例，对比DFS“一条路走到底”的递归回溯机制与BFS“层层扩张”的队列遍历策略，并提供完整代码逻辑，帮助开发者理解两种算法在路径搜索中的核心差异与应用场景。
深度优先搜索（Depth First Search，简称DFS）
深度优先搜索是一种图遍历算法，通常简称为「深度优先遍历」
为了更直观地理解，我们结合一个具体案例。如图所示，在一个九宫格地图中，绿色方块代表起点，红色方块代表终点，灰色区域及地图边界视为不可通行的障碍。任务要求从起点出发，每次仅能移动一格，寻找通往终点的路径。
采用 DFS 方法解决此问题时，根据图示，移动方向包括上下左右。我们预先约定一个优先级顺序：“左 > 上 > 右 > 下”，即优先尝试向左移动。若当前方向可走，则递归进入下一层；若未到达终点，则回溯至上一节点，并尝试下一个优先级的方向。同时，需对已走过的路径做标记，防止重复访问（即“不走回头路”）。
按照上述约定，路径从起点开始向左移动至位置 2。此时发现左侧无法通行，尝试向上和向下均受阻，而右侧因已走过被标记为不可通行，导致当前路径死胡同。当“无路可走”时，算法沿原路回溯，直到返回至存在未探索路径的节点，继续尝试其他方向。
回溯至初始节点 1 后，由于左侧已验证不通，且上、右方向亦不可行，算法转向下方移动，到达位置 6。在位置 6 处，依旧遵循“左 > 上 > 右 > 下”的优先级，左侧和右侧不可通行，上方已访问，因此继续向下移动。
继续向下移动至位置 9。在此节点，再次应用“左 > 上 > 右 > 下”策略，尝试向左发现可行，于是移动至位置 8。在位置 8 处，继续向左移动，最终成功抵达终点位置 7。
上述整个探索与回溯的过程，即为「深度优先遍历」的具体体现。
DFS 的核心机制在于状态回溯，其逻辑要点总结如下：
- 深度优先遍历的特性是：只要前方存在可行路径，便持续向前推进，直至遇到死胡同才进行回溯；
- 「无路可走」主要包含两种情形：① 遇到墙壁或边界障碍；② 遇到已访问过的节点；
- 当处于「无路可走」状态时，算法沿原路径回溯，直至回到尚有未探索分支的节点，并继续尝试未走过的路径；
- 部分路径未被完全遍历，是因为在搜索过程中已找到目标出口，程序随即终止；
- 「深度优先遍历」亦称「深度优先搜索」，其中“遍历”描述的是访问行为，“搜索”则指代其应用目的；
- 遍历并非高深莫测的概念，其本质是对所有可能情况进行逐一排查，从而确定「是否找到目标元素」或「未找到」。遍历也可理解为穷举，虽然穷举思维在人类直觉中看似朴素，但借助计算机强大的算力，穷举法能有效解决诸多专业领域难以处理的问题。
使用 DFS 算法解决前述九宫格问题的代码如下：
//我们以红点位置为坐标{0,0}，绿色位置坐标为{2,2}
//目标的坐标位置
let target = {
x: 0,
y: 0
};
//绿色起点的坐标位置
let currentLocation = {
x: 2,
y: 2
};
let used = []; //用来标记地图上哪些点是走过的
let reached = false; //是否能到达目标位置
// 表示灰色区域的格子
const illegalLocation = [
{ x: 0, y: 2 }, //序号1的坐标
{ x: 0, y: 1 }, //序号4的坐标
{ x: 1, y: 1 } //序号5的坐标
];
function isLegalLocation({ x, y }, illegalLocation) {
let flag = true;
//位置不能在地图坐标之外
if (x < 0 || x > 2 || y < 0 || y > 2) {
return (flag = false);
}
//不能走的路径
for (const { x: locX, y: locY } of illegalLocation) {
if (x === locX && y === locY) {
flag = false;
}
}
return flag;
}
//向左移动
function toLeft({ x, y }) {
return { x: x - 1, y };
}
//向上移动
function toTop({ x, y }) {
return { x, y: y + 1 };
}
//向右移动
function toRight({ x, y }) {
return { x: x + 1, y };
}
//向下移动
function toBottom({ x, y }) {
return { x, y: y - 1 };
}
function dfs(target, location, illegalLocation, used) {
// 如果当前位置与目标坐标相同表示可以抵达
if (Object.entries(target).toString() === Object.entries(location).toString()) {
console.log('reached', location);
return (reached = true);
}
let current = location;
const newIllegalLocation = illegalLocation.concat(used);
//假设按照“左>上>右>下”的顺序走
if (isLegalLocation(toLeft(location), newIllegalLocation)) {
current = toLeft(location);
} else if (isLegalLocation(toTop(location), newIllegalLocation)) {
current = toTop(location);
} else if (isLegalLocation(toRight(location), newIllegalLocation)) {
current = toRight(location);
} else if (isLegalLocation(toBottom(location), newIllegalLocation)) {
current = toBottom(location);
} else {
//走不通了就直接返回
return false
}
used.push(current); //将刚才走过的格子标记为已走过
return dfs(target, current, illegalLocation, used); //递归下去
}
dfs(target, currentLocation, illegalLocation, used);广度优先搜索（Breadth First Search，简称BFS）
广度优先搜索通常被称为「广度优先遍历」
BFS 与 DFS 的主要区别在于：BFS 在面临分叉路口时，会记录所有可能的分支，选择其中一个进入并记录其后续分支，随后返回重新选择另一个分支，如此重复。其图形化表示如下：
从绿色起点出发，记录所有直接相连的岔路口，并标记为“距离起点 1 步可达”。随后选择一个方向（如左侧序号为 2 的格子）深入，记录该节点可到达的方向，并标记为“距离起点 2 步可达”。
接着，回到起点下方的节点 1（序号为 6），记录其可到达的方向，同样标记为 2，因为这也是距离起点 2 步可达的区域。如此，所有“1 步”和“2 步”可达的区域均被搜索完毕，后续步骤同理，逐步标记出“3 步”、“4 步”可达的格子。
经过多轮扩展，最终成功找到路径，并计算出所有可行的路径方案。
注意：序号为 1、4、5 的格子为灰色区域，代表不可通行。
使用 BFS 算法解决前述九宫格问题的代码如下：
//我们以红点位置为坐标{0,0}，绿色位置坐标为{2,2}
//目标的坐标位置
let target = {
x: 0,
y: 0
};
//绿色起点的坐标位置
let currentLocation = {
x: 2,
y: 2
};
// 表示灰色区域的格子
const illegalLocation = [
{ x: 0, y: 2 }, //序号1的坐标
{ x: 0, y: 1 }, //序号4的坐标
{ x: 1, y: 1 } //序号5的坐标
];
function isLegalLocation({ x, y }, illegalLocation) {
let flag = true;
//位置不能在地图坐标之外
if (x < 0 || x > 2 || y < 0 || y > 2) {
return (flag = false);
}
//不能走的路径
for (const { x: locX, y: locY } of illegalLocation) {
if (x === locX && y === locY) {
flag = false;
}
}
return flag;
}
//向左移动
function toLeft({ x, y }) {
return { x: x - 1, y };
}
//向上移动
function toTop({ x, y }) {
return { x, y: y + 1 };
}
//向右移动
function toRight({ x, y }) {
return { x: x + 1, y };
}
//向下移动
function toBottom({ x, y }) {
return { x, y: y - 1 };
}
function bfs(target, location, illegalLocation) {
let reached = false; //是否能到达目标位置
let stack = [];
let searched = new Set(); //已经走过的格子
stack.push(location);
while (stack.length) {
let temp = stack.pop();
const newIllegalLocation = illegalLocation.concat([...searched]);
//假设按照“左>上>右>下”的顺序走
if (isLegalLocation(toLeft(temp), newIllegalLocation)) {
temp = toLeft(temp);
} else if (isLegalLocation(toTop(temp), newIllegalLocation)) {
temp = toTop(temp);
} else if (isLegalLocation(toRight(temp), newIllegalLocation)) {
temp = toRight(temp);
} else if (isLegalLocation(toBottom(temp), newIllegalLocation)) {
temp = toBottom(temp);
} else {
//没有通路就直接返回
return false
}
searched.add(temp);
stack.push(temp);
for (const { x: locX, y: locY } of searched) {
if (target.x === locX && target.y === locY) {
//如果当前位置与目标坐标相同表示可以抵达
reached = true;
console.log('reached: ', reached);
stack = [];
break;
}
}
}
return reached;
}
bfs(target, currentLocation, illegalLocation);「广度优先遍历」的思想在日常生活中随处可见：
- 例如寻找律师时，我们通常先在直接朋友中查找，若未找到，则扩大范围至朋友的朋友，直至寻得目标。
- 将石头投入平静水面，激起的一圈圈向外扩散的波纹，正是「广度优先遍历」特征的生动体现。
总结
- 「一条路走到底，不撞南墙不回头」是对 DFS 最直观的描述。因此，DFS 通常借助「递归」机制来实现。
- BFS 呈现出「层层向外扩张」的特点，遵循“先看到的节点先遍历，后看到的节点后遍历”的原则，因此 BFS 通常借助「队列」来实现。（具体操作为：遍历到一个节点时，若其存在左（右）孩子节点，则依次将其加入队列。）
- 总体而言，DFS 更适合目标明确且路径较短的搜索场景，而 BFS 更适合大范围或寻找最短路径的搜索场景。
到此这篇关于JavaScript遍历实现DFS算法和BFS算法的文章就介绍到这了,更多相关JavaScript实现DFS BFS内容请搜索本站以前的文章或继续浏览下面的相关文章希望大家以后多多支持本站！