跳到主要内容JavaScript 实现 BFS 广度优先搜索算法及可视化演示 | 极客日志JavaScriptAI大前端算法
JavaScript 实现 BFS 广度优先搜索算法及可视化演示
广度优先搜索（BFS）是解决无权图最短路径问题的经典算法，适用于网格寻路与状态空间搜索。本文通过 JavaScript 结合 Canvas 技术，实现了可交互的 BFS 可视化演示。代码包含完整的 HTML 结构与异步搜索逻辑，利用队列管理待访问节点，并通过 Set 记录已访问状态防止环路。引入异步等待机制以支持动画播放，直观展示搜索扩展与路径回溯过程。该实现适合作为算法教学案例或前端图形化应用的基础参考。
岁月神偷1 浏览 前言
在路径规划与图论问题中，广度优先搜索（BFS）是解决无权图最短路径问题的经典算法。相比 A*等启发式搜索，BFS 逻辑简单且能保证找到步数最少的路径，非常适合用于网格地图寻路或状态空间搜索。
本章我们将通过 JavaScript 完整实现 BFS 算法，并利用 Canvas 绘制交互网格，动态展示搜索过程。这种可视化方式能直观地帮助理解队列扩展、节点访问标记以及路径回溯的核心机制。
BFS 核心逻辑
BFS 的核心在于'层层推进'。我们使用一个队列来存储待访问的节点，每次从队头取出一个节点，检查其上下左右四个邻居。如果邻居未被访问且不是障碍物，则将其加入队列并记录路径信息。为了确保能找到最短路径，我们需要维护一个已访问集合（Set），避免重复处理同一个节点。
为了实现动画效果，我们在遍历过程中加入了异步等待，让浏览器有机会渲染每一帧的状态变化，从而形成流畅的视觉反馈。
代码实现
下面是一个完整的 HTML + JavaScript 示例。你可以直接保存为 .html 文件在浏览器中运行。
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>BFS Algorithm Visualization</title>
<style>
body {
font-family: Arial, sans-serif;
text-align: center;
margin: 20px;
}
canvas {
border: 1px solid #000;
margin: 10px auto;
display: block;
}
button {
padding: 10px ;
: ;
: pointer;
}
{
: ;
}
Breadth-First Search (BFS) Visualization
Set Start
Set End
Toggle Walls
Clear Grid
Run BFS
20px
margin
5px
cursor
.controls
margin
20px
</style>
</head>
<body>
<h1>
</h1>
<div class="controls">
<button id="start-btn">
</button>
<button id="end-btn">
</button>
<button id="wall-btn">
</button>
<button id="clear-btn">
</button>
<button id="run-btn">
</button>
</div>
<canvas id="grid" width="500" height="500">
</canvas>
<script>
const canvas = document.getElementById('grid');
const ctx = canvas.getContext('2d');
const gridSize = 20;
const cellSize = canvas.width / gridSize;
let grid = Array(gridSize).fill().map(() => Array(gridSize).fill(0));
let start = { x: 5, y: 5 };
let end = { x: 15, y: 15 };
let isSettingStart = false;
let isSettingEnd = false;
let isSettingWalls = false;
const colors = {
empty: '#fff',
wall: '#000',
start: '#00f',
end: '#f00',
visited: '#0ff',
path: '#ff0',
};
function initGrid() {
grid = Array(gridSize).fill().map(() => Array(gridSize).fill(0));
start = { x: 5, y: 5 };
end = { x: 15, y: 15 };
drawGrid();
}
function drawGrid() {
ctx.clearRect(0, 0, canvas.width, canvas.height);
for (let y = 0; y < gridSize; y++) {
for (let x = 0; x < gridSize; x++) {
ctx.strokeStyle = '#ddd';
ctx.strokeRect(x * cellSize, y * cellSize, cellSize, cellSize);
if (grid[y][x] === 1) {
ctx.fillStyle = colors.wall;
ctx.fillRect(x * cellSize, y * cellSize, cellSize, cellSize);
} else if (x === start.x && y === start.y) {
ctx.fillStyle = colors.start;
ctx.fillRect(x * cellSize, y * cellSize, cellSize, cellSize);
} else if (x === end.x && y === end.y) {
ctx.fillStyle = colors.end;
ctx.fillRect(x * cellSize, y * cellSize, cellSize, cellSize);
} else if (grid[y][x] === 2) {
ctx.fillStyle = colors.visited;
ctx.fillRect(x * cellSize, y * cellSize, cellSize, cellSize);
} else if (grid[y][x] === 3) {
ctx.fillStyle = colors.path;
ctx.fillRect(x * cellSize, y * cellSize, cellSize, cellSize);
}
}
}
}
async function bfs() {
const queue = [{ x: start.x, y: start.y, path: [] }];
const visited = new Set();
visited.add(`${start.x},${start.y}`);
const directions = [
{ dx: 1, dy: 0 },
{ dx: -1, dy: 0 },
{ dx: 0, dy: 1 },
{ dx: 0, dy: -1 }
];
while (queue.length > 0) {
const current = queue.shift();
const { x, y, path } = current;
if (!(x === start.x && y === start.y) && !(x === end.x && y === end.y)) {
grid[y][x] = 2;
drawGrid();
await new Promise(resolve => setTimeout(resolve, 50));
}
if (x === end.x && y === end.y) {
for (const { x, y } of path) {
grid[y][x] = 3;
drawGrid();
await new Promise(resolve => setTimeout(resolve, 100));
}
return;
}
for (const dir of directions) {
const nx = x + dir.dx;
const ny = y + dir.dy;
if (nx >= 0 && nx < gridSize && ny >= 0 && ny < gridSize &&
grid[ny][nx] !== 1 && !visited.has(`${nx},${ny}`)) {
visited.add(`${nx},${ny}`);
queue.push({ x: nx, y: ny, path: [...path, { x, y }] });
}
}
}
alert("No path found!");
}
canvas.addEventListener('click', (e) => {
const x = Math.floor(e.offsetX / cellSize);
const y = Math.floor(e.offsetY / cellSize);
if (isSettingStart) {
start = { x, y };
} else if (isSettingEnd) {
end = { x, y };
} else if (isSettingWalls) {
grid[y][x] = grid[y][x] === 1 ? 0 : 1;
}
drawGrid();
});
document.getElementById('start-btn').addEventListener('click', () => {
isSettingStart = true;
isSettingEnd = false;
isSettingWalls = false;
});
document.getElementById('end-btn').addEventListener('click', () => {
isSettingStart = false;
isSettingEnd = true;
isSettingWalls = false;
});
document.getElementById('wall-btn').addEventListener('click', () => {
isSettingStart = false;
isSettingEnd = false;
isSettingWalls = true;
});
document.getElementById('clear-btn').addEventListener('click', initGrid);
document.getElementById('run-btn').addEventListener('click', bfs);
initGrid();
</script>
</body>
</html>
关键点解析
- 异步控制：
bfs 函数使用了 async/await 配合 setTimeout 和 Promise。这是为了让浏览器在执行耗时循环时能够刷新 UI，否则整个搜索会瞬间完成，无法看到动画效果。
- 状态管理：
grid 数组不仅存储障碍物信息（1），还用来临时标记已访问节点（2）和最终路径（3）。每次状态变更都调用 drawGrid 重绘。
- 交互设计：通过点击按钮切换模式（设置起点、终点、墙壁），最后点击 Run 触发搜索。这种设计降低了测试门槛，方便快速验证不同场景。
实际开发中，如果遇到更复杂的地图或性能要求，可以将网格逻辑封装成类，或者使用 Web Worker 处理计算以避免阻塞主线程。但对于学习算法原理，这个 Demo 已经足够清晰了。
相关免费在线工具
- 加密/解密文本
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
- RSA密钥对生成器
生成新的随机RSA私钥和公钥pem证书。 在线工具，RSA密钥对生成器在线工具，online
- Mermaid 预览与可视化编辑
基于 Mermaid.js 实时预览流程图、时序图等图表，支持源码编辑与即时渲染。 在线工具，Mermaid 预览与可视化编辑在线工具，online
- 随机西班牙地址生成器
随机生成西班牙地址（支持马德里、加泰罗尼亚、安达卢西亚、瓦伦西亚筛选），支持数量快捷选择、显示全部与下载。 在线工具，随机西班牙地址生成器在线工具，online
- Gemini 图片去水印
基于开源反向 Alpha 混合算法去除 Gemini/Nano Banana 图片水印，支持批量处理与下载。 在线工具，Gemini 图片去水印在线工具，online
- Keycode 信息
查找任何按下的键的javascript键代码、代码、位置和修饰符。 在线工具，Keycode 信息在线工具，online
