用C语言手搓迷宫求解器：DFS和BFS算法实战对比（附完整代码）

用C语言手搓迷宫求解器：DFS和BFS算法实战对比（附完整代码）

第一次接触图遍历算法时，很多人都会被那些抽象的概念和数学符号搞得晕头转向。直到有一天，我在纸上随手画了个迷宫，突然意识到——这不就是图的遍历吗？从入口到出口的路径搜索，本质上就是在图中寻找两个节点间的连通路径。这种具象化的理解让我茅塞顿开，也促使我开发了这个迷宫求解器项目。

1. 迷宫的数据结构设计

迷宫本质上是一个二维矩阵，我们可以用最简单的字符数组来表示。约定用'#'表示墙壁，'.'表示可通行路径，'S'和'E'分别代表起点和终点：

#define MAX_SIZE 100 char maze[MAX_SIZE][MAX_SIZE]; int rows, cols; // 迷宫实际行数和列数

读取迷宫数据的函数示例：

void read_maze() { printf("输入迷宫行数和列数: "); scanf("%d %d", &rows, &cols); getchar(); // 消耗换行符 printf("逐行输入迷宫(每行%d个字符):\n", cols); for(int i=0; i<rows; i++) { for(int j=0; j<cols; j++) { maze[i][j] = getchar(); } getchar(); // 消耗换行符 } }

为了记录访问状态和路径回溯，我们需要两个辅助数组：

int visited[MAX_SIZE][MAX_SIZE]; // 访问标记数组 Point parent[MAX_SIZE][MAX_SIZE]; // 路径父节点记录 typedef struct { int x, y; } Point;

2. 深度优先搜索(DFS)实现

DFS就像一个人在迷宫中探索，遇到岔路时选择一条路走到底，碰壁后再回溯。这种"不撞南墙不回头"的策略用递归实现非常直观：

int dfs(Point curr, Point end) { // 越界检查 if(curr.x <0 || curr.x >= rows || curr.y <0 || curr.y >= cols) return 0; // 遇到墙壁或已访问 if(maze[curr.x][curr.y] == '#' || visited[curr.x][curr.y]) return 0; // 标记已访问 visited[curr.x][curr.y] = 1; // 找到终点 if(curr.x == end.x && curr.y == end.y) return 1; // 四个方向探索 Point directions[4] = {{-1,0}, {1,0}, {0,-1}, {0,1}}; for(int i=0; i<4; i++) { Point next = {curr.x + directions[i].x, curr.y + directions[i].y}; if(dfs(next, end)) { parent[next.x][next.y] = curr; // 记录路径 return 1; } } return 0; }

非递归版本使用显式栈实现，更适合大型迷宫：

int dfs_stack(Point start, Point end) { Stack s; init_stack(&s); push_stack(&s, start); while(!is_stack_empty(&s)) { Point curr = pop_stack(&s); // 终点检查 if(curr.x == end.x && curr.y == end.y) return 1; if(!visited[curr.x][curr.y]) { visited[curr.x][curr.y] = 1; // 逆序压栈保证探索顺序 Point directions[4] = {{0,1}, {0,-1}, {1,0}, {-1,0}}; for(int i=0; i<4; i++) { Point next = {curr.x+directions[i].x, curr.y+directions[i].y}; if(is_valid(next)) { parent[next.x][next.y] = curr; push_stack(&s, next); } } } } return 0; }

DFS的特点总结：

• 空间复杂度：O(h)，h为迷宫最大深度
• 路径特性：找到的路径通常较长且曲折
• 适用场景：迷宫结构较深、内存受限时

3. 广度优先搜索(BFS)实现

BFS则像水波纹一样从起点向外扩散，总是先探索距离起点最近的位置，使用队列实现：

int bfs(Point start, Point end) { Queue q; init_queue(&q); enqueue(&q, start); visited[start.x][start.y] = 1; Point directions[4] = {{-1,0}, {1,0}, {0,-1}, {0,1}}; while(!is_queue_empty(&q)) { Point curr = dequeue(&q); // 到达终点 if(curr.x == end.x && curr.y == end.y) return 1; // 探索四个方向 for(int i=0; i<4; i++) { Point next = {curr.x + directions[i].x, curr.y + directions[i].y}; if(is_valid(next) && !visited[next.x][next.y]) { visited[next.x][next.y] = 1; parent[next.x][next.y] = curr; enqueue(&q, next); } } } return 0; }

BFS的典型特征：

• 空间复杂度：O(w)，w为迷宫最大宽度
• 路径特性：总能找到最短路径
• 适用场景：需要最短路径或迷宫较宽时

4. 两种算法的实战对比

我们在三个不同复杂度的迷宫上测试两种算法：

关键差异分析：

1. 路径最优性：

   • BFS天然保证找到最短路径
   • DFS找到的路径长度通常比最优解长30%-50%

2. 内存消耗：

   // DFS递归深度与迷宫深度成正比 void dfs(Point p) { // 每次递归调用消耗~48字节栈空间 dfs(next_point); } // BFS队列存储所有待探索边界点 Queue q; // 可能存储O(n²)个点

3. 代码复杂度：

   • DFS递归版本仅需10-15行核心代码
   • BFS需要完整实现队列数据结构

4. 适用场景选择：

   • 当需要最短路径时：选择BFS
   • 当内存受限时：选择DFS非递归版
   • 当迷宫存在环路时：两者都需要visited数组
   • 当需要所有可能路径时：修改DFS更合适

5. 可视化与路径回溯

找到路径后，我们可以用ASCII字符直观展示解决方案：

void print_path(Point start, Point end) { // 反向追溯路径 Point curr = end; while(!(curr.x == start.x && curr.y == start.y)) { maze[curr.x][curr.y] = '*'; // 标记路径 curr = parent[curr.x][curr.y]; } maze[start.x][start.y] = 'S'; // 打印带路径的迷宫 for(int i=0; i<rows; i++) { for(int j=0; j<cols; j++) { printf("%c", maze[i][j]); } printf("\n"); } }

示例输出：

##### #S*.# #*### #*..# #**E# #####

6. 性能优化技巧

1. 双向BFS：从起点和终点同时开始搜索，相遇时停止

   int bidirectional_bfs(Point start, Point end) { Queue q_start, q_end; init_queue(&q_start); init_queue(&q_end); enqueue(&q_start, start); enqueue(&q_end, end); visited_start[start.x][start.y] = 1; visited_end[end.x][end.y] = 1; while(!is_queue_empty(&q_start) && !is_queue_empty(&q_end)) { if(expand_level(&q_start, visited_start, visited_end)) return 1; if(expand_level(&q_end, visited_end, visited_start)) return 1; } return 0; }

2. 启发式搜索(A)*：结合BFS和启发式函数

   int heuristic(Point a, Point b) { return abs(a.x - b.x) + abs(a.y - b.y); // 曼哈顿距离 }

3. 内存优化：使用位图压缩visited数组

   unsigned char visited_bitmap[MAX_SIZE][MAX_SIZE/8+1]; void set_visited(int x, int y) { visited_bitmap[x][y/8] |= (1 << (y%8)); }

7. 完整代码实现

以下是整合了DFS和BFS的完整迷宫求解器：

#include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX_SIZE 100 typedef struct { int x, y; } Point; char maze[MAX_SIZE][MAX_SIZE]; int rows, cols; Point parent[MAX_SIZE][MAX_SIZE]; int visited[MAX_SIZE][MAX_SIZE]; // 队列实现 typedef struct { Point data[MAX_SIZE*MAX_SIZE]; int front, rear; } Queue; void init_queue(Queue *q) { q->front = q->rear = 0; } int is_queue_empty(Queue *q) { return q->front == q->rear; } void enqueue(Queue *q, Point p) { q->data[q->rear++] = p; } Point dequeue(Queue *q) { return q->data[q->front++]; } int is_valid(Point p) { return p.x >=0 && p.x < rows && p.y >=0 && p.y < cols && maze[p.x][p.y] != '#' && !visited[p.x][p.y]; } int bfs(Point start, Point end) { Queue q; init_queue(&q); enqueue(&q, start); visited[start.x][start.y] = 1; Point directions[4] = {{-1,0}, {1,0}, {0,-1}, {0,1}}; while(!is_queue_empty(&q)) { Point curr = dequeue(&q); if(curr.x == end.x && curr.y == end.y) return 1; for(int i=0; i<4; i++) { Point next = {curr.x + directions[i].x, curr.y + directions[i].y}; if(is_valid(next)) { visited[next.x][next.y] = 1; parent[next.x][next.y] = curr; enqueue(&q, next); } } } return 0; } int dfs(Point curr, Point end) { if(!is_valid(curr)) return 0; visited[curr.x][curr.y] = 1; if(curr.x == end.x && curr.y == end.y) return 1; Point directions[4] = {{-1,0}, {1,0}, {0,-1}, {0,1}}; for(int i=0; i<4; i++) { Point next = {curr.x + directions[i].x, curr.y + directions[i].y}; if(dfs(next, end)) { parent[next.x][next.y] = curr; return 1; } } return 0; } void print_path(Point start, Point end) { Point curr = end; while(!(curr.x == start.x && curr.y == start.y)) { maze[curr.x][curr.y] = '*'; curr = parent[curr.x][curr.y]; } for(int i=0; i<rows; i++) { for(int j=0; j<cols; j++) { printf("%c", maze[i][j]); } printf("\n"); } } int main() { printf("输入迷宫行数和列数: "); scanf("%d %d", &rows, &cols); getchar(); Point start, end; printf("输入迷宫地图(%d行×%d列):\n", rows, cols); for(int i=0; i<rows; i++) { for(int j=0; j<cols; j++) { maze[i][j] = getchar(); if(maze[i][j] == 'S') start = (Point){i,j}; if(maze[i][j] == 'E') end = (Point){i,j}; } getchar(); } printf("\n选择算法: 1.BFS 2.DFS\n"); int choice; scanf("%d", &choice); memset(visited, 0, sizeof(visited)); int found = 0; if(choice == 1) { found = bfs(start, end); printf("\nBFS结果:\n"); } else { found = dfs(start, end); printf("\nDFS结果:\n"); } if(found) { print_path(start, end); } else { printf("找不到路径!\n"); } return 0; }

这个项目最让我惊喜的是，当我把这个迷宫求解器展示给刚开始学编程的表弟时，他居然通过调整迷宫结构和观察算法行为，自己总结出了DFS和BFS的特性差异。这种通过具体问题理解抽象概念的方式，确实比单纯的理论讲解有效得多。