JAVA BFS/DFS 可视化
大约 10 分钟
BFS/DFS 可视化
基于JAVA的BFS/DFS 可视化
一、简介
本系统是一个基于 Java GUI 的迷宫求解可视化演示程序，旨在通过直观的动画效果展示深度优先搜索 (DFS) 和广度优先搜索 (BFS) 两种经典算法在迷宫寻路问题中的应用过程。系统能够生成随机迷宫，并通过不同颜色标识搜索过程中的各个状态：DFS 使用浅红色表示搜索路径、浅灰色表示回溯路径；BFS 使用浅蓝色表示搜索路径；最终的正确路径则用黄色高亮显示。用户可以通过界面按钮控制迷宫生成、算法执行和系统重置等操作。
二、视频演示
1. DFS算法
2. BFS算法
二、核心思路
（一）DFS（深度优先搜索）
1. 核心思想
“先走到底，再回头”：从起点出发，优先沿着一个方向深度探索，直到遇到死胡同（无法前进），再回溯到上一个分支点，选择其他未探索的方向继续搜索，直到找到终点。算法依赖 栈（Stack） 数据结构（或递归的调用栈）来实现路径的记录与回溯。
2. 系统中的实现逻辑
对应代码：executeDFS() 方法 + dfsFindPathWithBacktrack() 递归方法
（二）BFS（广度优先搜索）
1. 核心思想
“先扫一层，再扫下一层”：从起点出发，优先逐层扩散搜索 —— 先探索起点周围所有相邻的位置（第一层），再探索这些位置的相邻位置（第二层），以此类推，直到找到终点。算法依赖 队列（Queue） 数据结构来实现 “逐层推进”，同时通过前驱数组记录路径。
2. 系统中的实现逻辑
对应代码：executeBFS() 方法。
三、源代码
import javax.swing.*;
import java.awt.*;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.util.*;
import java.util.List;
public class MazeMouseVisualizer extends JFrame {
//底层思路：将单元格设为8种状态来通过函数改变单元个格的状态实现迷宫的各项功能。
// 迷宫常量定义
private static final int CELL_SIZE = 10; // 单元格大小（像素）
private static final int MAZE_ROWS = 61; // 迷宫行数（建议奇数）
private static final int MAZE_COLS = 61; // 迷宫列数（建议奇数）
// 单元格类型（扩展为更细致的状态）
private static final int PATH = 0; // 通路
private static final int WALL = 1; // 墙壁
private static final int START = 2; // 起点（老鼠）
private static final int END = 3; // 终点（食物）
private static final int DFS_SEARCH = 4; // DFS搜索中（浅红色）
private static final int DFS_WRONG = 5; // DFS错误路径（浅灰色）
private static final int BFS_SEARCH = 6; // BFS搜索中（浅蓝色）
private static final int FINAL_PATH = 7; // 最终正确路径（黄色）
// 方向：上、右、下、左（坐标偏移）
private static final int[][] DIRECTIONS = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
private Random random = new Random();
// 迷宫数据
private int[][] mazeGrid; // 迷宫网格
private int startX = 1, startY = 1; // 起点坐标（左上角）
private int endX = MAZE_ROWS - 2, endY = MAZE_COLS - 2; // 终点坐标（右下角）
private List<int[]> dfsSearchSteps; // DFS搜索步骤（含回溯）
private List<int[]> bfsSearchSteps; // BFS搜索步骤
private List<int[]> finalPath; // 最终正确路径
private boolean isAnimating = false; // 是否正在执行动画
// GUI 组件
private MazePanel mazePanel;
private JButton generateBtn;
private JButton dfsBtn;
private JButton bfsBtn;
private JButton resetBtn;
private JLabel infoLabel;
// 自定义颜色（精准匹配需求）
private static final Color LIGHT_RED = new Color(255, 182, 193); // 浅红色（DFS搜索）
private static final Color LIGHT_GRAY = new Color(202, 195, 195); // 浅灰色（DFS回溯错误路径）
private static final Color LIGHT_BLUE = new Color(173, 216, 230); // 浅蓝色（BFS搜索）
private static final Color YELLOW = new Color(255, 255, 0); // 黄色（最终路径）
private static final Color DARK_GREEN = new Color(0, 100, 0); // 深绿色（老鼠图标）
private static final Color DARK_RED = new Color(139, 0, 0); // 深红色（食物图标）
public MazeMouseVisualizer() {
// 初始化窗口
setTitle("迷宫老鼠找食物（DFS/BFS 可视化演示）");
setSize(MAZE_COLS * CELL_SIZE + 40, MAZE_ROWS * CELL_SIZE + 120);
setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
setLocationRelativeTo(null); // 窗口居中
setLayout(new BorderLayout());
// 初始化迷宫面板
mazePanel = new MazePanel();
add(mazePanel, BorderLayout.CENTER);
// 初始化控制面板
JPanel controlPanel = new JPanel();
controlPanel.setPreferredSize(new Dimension(MAZE_COLS * CELL_SIZE, 60));
controlPanel.setLayout(new FlowLayout(FlowLayout.CENTER, 15, 15));
// 创建按钮
generateBtn = new JButton("生成随机迷宫");
dfsBtn = new JButton("执行DFS搜索");
bfsBtn = new JButton("执行BFS搜索");
resetBtn = new JButton("重置演示");
infoLabel = new JLabel("请先生成迷宫", JLabel.CENTER);
infoLabel.setForeground(Color.BLUE);
// 设置按钮状态
dfsBtn.setEnabled(false);
bfsBtn.setEnabled(false);
resetBtn.setEnabled(false);
// 添加组件到窗口
controlPanel.add(generateBtn);
controlPanel.add(dfsBtn);
controlPanel.add(bfsBtn);
controlPanel.add(resetBtn);
add(controlPanel, BorderLayout.SOUTH);
add(infoLabel, BorderLayout.NORTH);
// 注册按钮事件
registerEvents();
// 初始化迷宫
mazeGrid = new int[MAZE_ROWS][MAZE_COLS];
for (int i = 0; i < MAZE_ROWS; i++) {
Arrays.fill(mazeGrid[i], WALL);
}
}
//这里去注册按钮
private void registerEvents() {
// 生成迷宫按钮
generateBtn.addActionListener(e -> {
if (!isAnimating) {
generateMaze();
mazePanel.repaint();
infoLabel.setText("迷宫生成完成，可执行搜索算法");
dfsBtn.setEnabled(true);
bfsBtn.setEnabled(true);
resetBtn.setEnabled(true);
}
});
// DFS搜索按钮
dfsBtn.addActionListener(e -> {
if (!isAnimating && mazeGrid != null) {
executeDFS();
}
});
// BFS搜索按钮
bfsBtn.addActionListener(e -> {
if (!isAnimating && mazeGrid != null) {
executeBFS();
}
});
// 重置按钮
resetBtn.addActionListener(e -> {
if (!isAnimating) {
resetMaze();
mazePanel.repaint();
infoLabel.setText("迷宫已重置，可重新生成或搜索");
dfsBtn.setEnabled(true);
bfsBtn.setEnabled(true);
}
});
}
//这里去生成迷宫
private void generateMaze() {
// 初始化全为墙壁
for (int i = 0; i < MAZE_ROWS; i++) {
Arrays.fill(mazeGrid[i], WALL);
}
// 从(1,1)开始递归挖路
dfsGenerateMaze(startX, startY);
// 设置起点和终点
mazeGrid[startX][startY] = START;
mazeGrid[endX][endY] = END;
}
//递归算法
private void dfsGenerateMaze(int x, int y) {
// 标记当前位置为通路
mazeGrid[x][y] = PATH;
// 打乱方向顺序（实现随机生成）
List<int[]> dirs = new ArrayList<>(Arrays.asList(DIRECTIONS));
Collections.shuffle(dirs);
for (int[] dir : dirs) {
// 计算两步后的位置（跳过中间墙壁）
int nx = x + dir[0] * 2;
int ny = y + dir[1] * 2;
// 判断是否在迷宫范围内且未被访问
if (nx > 0 && nx < MAZE_ROWS - 1 && ny > 0 && ny < MAZE_COLS - 1 && mazeGrid[nx][ny] == WALL) {
// 打通中间墙壁
mazeGrid[x + dir[0]][y + dir[1]] = PATH;
// 递归处理下一步
dfsGenerateMaze(nx, ny);
}
}
}
//DFS
private void executeDFS() {
isAnimating = true;
setButtonsEnabled(false, false, false, false);
infoLabel.setText("DFS搜索中...（先深后广，不保证最短路径）");
// 重置搜索痕迹
resetSearchTrace();
mazePanel.repaint();
boolean[][] visited = new boolean[MAZE_ROWS][MAZE_COLS];
dfsSearchSteps = new ArrayList<>();
finalPath = new ArrayList<>();
Stack<int[]> pathStack = new Stack<>();
// 执行DFS递归查找（带回溯标记）
dfsFindPathWithBacktrack(startX, startY, visited, pathStack);
// 启动DFS专属动画（含搜索和回溯）
startDfsAnimation();
}
//DFS递归查找路径（带回溯标记，记录错误路径）
private boolean dfsFindPathWithBacktrack(int x, int y, boolean[][] visited, Stack<int[]> pathStack) {
// 终止条件：越界、墙壁、已访问
if (x < 0 || x >= MAZE_ROWS || y < 0 || y >= MAZE_COLS || mazeGrid[x][y] == WALL || visited[x][y]) {
return false;
}
// 标记已访问并记录搜索步骤（浅红色）
visited[x][y] = true;
dfsSearchSteps.add(new int[]{x, y, DFS_SEARCH}); // 第三个值标记状态：搜索中
pathStack.push(new int[]{x, y});
// 找到终点
if (x == endX && y == endY) {
finalPath.addAll(new ArrayList<>(pathStack));
return true;
}
// 遍历四个方向
for (int[] dir : DIRECTIONS) {
int nx = x + dir[0];
int ny = y + dir[1];
if (dfsFindPathWithBacktrack(nx, ny, visited, pathStack)) {
return true;
}
}
// 回溯：当前路径是死胡同，记录错误路径（浅灰色）
int[] wrongPos = pathStack.pop();
dfsSearchSteps.add(new int[]{wrongPos[0], wrongPos[1], DFS_WRONG}); // 第三个值标记状态：错误路径
return false;
}
//执行BFS搜索
private void executeBFS() {
isAnimating = true;
setButtonsEnabled(false, false, false, false);
infoLabel.setText("BFS搜索中...（先广后深，保证最短路径）");
// 重置搜索痕迹
resetSearchTrace();
mazePanel.repaint();
boolean[][] visited = new boolean[MAZE_ROWS][MAZE_COLS];
bfsSearchSteps = new ArrayList<>();
finalPath = new ArrayList<>();
Queue<int[]> queue = new LinkedList<>();
int[][] prev = new int[MAZE_ROWS * MAZE_COLS][2]; // 记录前驱节点，用于回溯路径
// 初始化前驱节点为-1（无效值）
for (int[] p : prev) {
Arrays.fill(p, -1);
}
// 初始化队列
queue.offer(new int[]{startX, startY});
visited[startX][startY] = true;
bfsSearchSteps.add(new int[]{startX, startY});
boolean found = false;
// BFS核心逻辑
while (!queue.isEmpty() && !found) {
int[] curr = queue.poll();
int x = curr[0];
int y = curr[1];
for (int[] dir : DIRECTIONS) {
int nx = x + dir[0];
int ny = y + dir[1];
if (nx >= 0 && nx < MAZE_ROWS && ny >= 0 && ny < MAZE_COLS
&& mazeGrid[nx][ny] != WALL && !visited[nx][ny]) {
visited[nx][ny] = true;
bfsSearchSteps.add(new int[]{nx, ny});
queue.offer(new int[]{nx, ny});
prev[nx * MAZE_COLS + ny] = new int[]{x, y}; // 记录前驱
// 找到终点
if (nx == endX && ny == endY) {
found = true;
break;
}
}
}
}
// 回溯生成最终路径
if (found) {
Stack<int[]> stack = new Stack<>();
int x = endX;
int y = endY;
while (x != -1 && y != -1 && (x != startX || y != startY)) {
stack.push(new int[]{x, y});
int[] p = prev[x * MAZE_COLS + y];
x = p[0];
y = p[1];
}
stack.push(new int[]{startX, startY});
// 反转得到正序路径（起点→终点）
while (!stack.isEmpty()) {
finalPath.add(stack.pop());
}
}
// 启动BFS专属动画
startBfsAnimation();
}
//启动DFS动画（先展示浅红搜索，再展示浅灰回溯，最后展示黄色路径）
private void startDfsAnimation() {
int delay = 30; // 动画延迟（毫秒/步）
int[] index = {0}; // 用数组存储索引（满足有效final）
javax.swing.Timer dfsTimer = new javax.swing.Timer(delay, new ActionListener() {
@Override
public void actionPerformed(ActionEvent e) {
if (index[0] >= dfsSearchSteps.size()) {
((javax.swing.Timer) e.getSource()).stop();
// DFS搜索/回溯完成，启动最终路径动画
startFinalPathAnimation("DFS");
return;
}
// 获取步骤信息（x, y, 状态）
int[] step = dfsSearchSteps.get(index[0]);
int x = step[0];
int y = step[1];
int state = step[2];
// 跳过起点和终点，标记对应状态
if (mazeGrid[x][y] != START && mazeGrid[x][y] != END) {
mazeGrid[x][y] = state;
}
mazePanel.repaint();
index[0]++;
}
});
dfsTimer.start();
}
//启动BFS动画（展示浅蓝搜索，最后展示黄色路径）
private void startBfsAnimation() {
int delay = 30; // 动画延迟（毫秒/步）
int[] index = {0}; // 用数组存储索引（满足有效final）
javax.swing.Timer bfsTimer = new javax.swing.Timer(delay, new ActionListener() {
@Override
public void actionPerformed(ActionEvent e) {
if (index[0] >= bfsSearchSteps.size()) {
((javax.swing.Timer) e.getSource()).stop();
// BFS搜索完成，启动最终路径动画
startFinalPathAnimation("BFS");
return;
}
// 标记BFS搜索步骤（浅蓝色）
int[] pos = bfsSearchSteps.get(index[0]);
int x = pos[0];
int y = pos[1];
if (mazeGrid[x][y] != START && mazeGrid[x][y] != END) {
mazeGrid[x][y] = BFS_SEARCH;
}
mazePanel.repaint();
index[0]++;
}
});
bfsTimer.start();
}
//启动最终路径动画（黄色标记正确路径）
private void startFinalPathAnimation(String algorithm) {
int delay = 50; // 路径动画延迟（更慢，便于观察）
int[] index = {0};
javax.swing.Timer pathTimer = new javax.swing.Timer(delay, new ActionListener() {
@Override
public void actionPerformed(ActionEvent e) {
if (index[0] >= finalPath.size()) {
((javax.swing.Timer) e.getSource()).stop();
isAnimating = false;
// 动画完成，更新信息（仅保留算法类型和路径长度）
String info = algorithm + "搜索完成！";
info += " 路径长度：" + finalPath.size();
info += algorithm.equals("BFS") ? "（最短路径）" : "（不保证最短）";
infoLabel.setText(info);
infoLabel.setForeground(Color.RED);
setButtonsEnabled(true, true, true, true);
return;
}
// 标记最终正确路径（黄色）
int[] pos = finalPath.get(index[0]);
int x = pos[0];
int y = pos[1];
if (mazeGrid[x][y] != START && mazeGrid[x][y] != END) {
mazeGrid[x][y] = FINAL_PATH;
}
mazePanel.repaint();
index[0]++;
}
});
pathTimer.start();
}
//重置迷宫搜索痕迹（保留迷宫结构和起止点）
private void resetSearchTrace() {
for (int i = 0; i < MAZE_ROWS; i++) {
for (int j = 0; j < MAZE_COLS; j++) {
if (mazeGrid[i][j] == DFS_SEARCH || mazeGrid[i][j] == DFS_WRONG
|| mazeGrid[i][j] == BFS_SEARCH || mazeGrid[i][j] == FINAL_PATH) {
mazeGrid[i][j] = PATH;
}
}
}
// 恢复起点和终点
mazeGrid[startX][startY] = START;
mazeGrid[endX][endY] = END;
}
//完全重置迷宫（清空所有搜索相关数据）
private void resetMaze() {
resetSearchTrace();
dfsSearchSteps = null;
bfsSearchSteps = null;
finalPath = null;
infoLabel.setForeground(Color.BLUE);
}
//批量设置按钮启用状态
private void setButtonsEnabled(boolean generate, boolean dfs, boolean bfs, boolean reset) {
generateBtn.setEnabled(generate);
dfsBtn.setEnabled(dfs);
bfsBtn.setEnabled(bfs);
resetBtn.setEnabled(reset);
}
//迷宫绘制面板（自定义绘制，精准匹配颜色需求）
class MazePanel extends JPanel {
@Override
protected void paintComponent(Graphics g) {
super.paintComponent(g);
// 绘制迷宫网格
for (int i = 0; i < MAZE_ROWS; i++) {
for (int j = 0; j < MAZE_COLS; j++) {
int x = j * CELL_SIZE;
int y = i * CELL_SIZE;
// 根据单元格类型设置对应颜色
switch (mazeGrid[i][j]) {
case WALL:
g.setColor(Color.BLACK);
break;
case START:
g.setColor(Color.GREEN);
break;
case END:
g.setColor(Color.RED);
break;
case DFS_SEARCH:
g.setColor(LIGHT_RED); // DFS搜索中：浅红色
break;
case DFS_WRONG:
g.setColor(LIGHT_GRAY); // DFS错误路径：浅灰色
break;
case BFS_SEARCH:
g.setColor(LIGHT_BLUE); // BFS搜索中：浅蓝色
break;
case FINAL_PATH:
g.setColor(YELLOW); // 最终正确路径：黄色
break;
default: // PATH
g.setColor(Color.WHITE);
break;
}
// 绘制单元格
g.fillRect(x, y, CELL_SIZE, CELL_SIZE);
// 这里我选择去掉来优化UI
// 绘制单元格边框（增强视觉层次感）
// g.setColor(Color.DARK_GRAY);
// g.drawRect(x, y, CELL_SIZE, CELL_SIZE);
}
}
// 绘制老鼠（起点）和食物（终点）图标
drawMouseAndFood(g);
}
//绘制老鼠和食物图标，增强可视化效果
private void drawMouseAndFood(Graphics g) {
// 老鼠（深绿色圆形，起点）
g.setColor(DARK_GREEN);
int mouseX = startY * CELL_SIZE + CELL_SIZE / 4;
int mouseY = startX * CELL_SIZE + CELL_SIZE / 4;
g.fillOval(mouseX, mouseY, CELL_SIZE / 2, CELL_SIZE / 2);
// 食物（深红色圆形，终点）
g.setColor(DARK_RED);
int foodX = endY * CELL_SIZE + CELL_SIZE / 4;
int foodY = endX * CELL_SIZE + CELL_SIZE / 4;
g.fillOval(foodX, foodY, CELL_SIZE / 2, CELL_SIZE / 2);
}
}
//主方法：启动程序（在EDT线程中运行，保证Swing线程安全）
public static void main(String[] args) {
SwingUtilities.invokeLater(() -> {
MazeMouseVisualizer gui = new MazeMouseVisualizer();
gui.setVisible(true);
});
}
}