用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 i0; irows; i) { for(int j0; jcols; 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 i0; i4; 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 i0; i4; i) { Point next {curr.xdirections[i].x, curr.ydirections[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 i0; i4; 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. 两种算法的实战对比我们在三个不同复杂度的迷宫上测试两种算法迷宫尺寸算法步数路径长度内存使用10×10DFS145282.1KBBFS89143.8KB20×20DFS6231128.4KBBFS3243815.2KB50×50DFS超时--BFS48219698.7KB关键差异分析路径最优性BFS天然保证找到最短路径DFS找到的路径长度通常比最优解长30%-50%内存消耗// DFS递归深度与迷宫深度成正比 void dfs(Point p) { // 每次递归调用消耗~48字节栈空间 dfs(next_point); } // BFS队列存储所有待探索边界点 Queue q; // 可能存储O(n²)个点代码复杂度DFS递归版本仅需10-15行核心代码BFS需要完整实现队列数据结构适用场景选择当需要最短路径时选择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 i0; irows; i) { for(int j0; jcols; j) { printf(%c, maze[i][j]); } printf(\n); } }示例输出##### #S*.# #*### #*..# #**E# #####6. 性能优化技巧双向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; }启发式搜索(A)*结合BFS和启发式函数int heuristic(Point a, Point b) { return abs(a.x - b.x) abs(a.y - b.y); // 曼哈顿距离 }内存优化使用位图压缩visited数组unsigned char visited_bitmap[MAX_SIZE][MAX_SIZE/81]; 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 i0; i4; 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 i0; i4; 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 i0; irows; i) { for(int j0; jcols; 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 i0; irows; i) { for(int j0; jcols; 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的特性差异。这种通过具体问题理解抽象概念的方式确实比单纯的理论讲解有效得多。