随机深度优先搜索是深度优先搜索的变种，通过在每一步随机选择邻接节点来增加路径的不可预测性。该算法天然适合生成或解决迷宫问题，因其倾向于生成长而曲折的路径。
核心特点：
- 使用栈（显式或隐式）实现回溯
- 随机选择邻接节点顺序
- 时间复杂度为O(V+E)，空间复杂度为O(V)
C++实现关键步骤
数据结构定义
#include <iostream> #include <vector> #include <stack> #include <cstdlib> #include <ctime> #include <algorithm> struct Cell { int x, y; bool visited = false; bool top_wall = true, bottom_wall = true; bool left_wall = true, right_wall = true; };迷宫初始化
void initMaze(std::vector<std::vector<Cell>>& maze, int width, int height) { maze.resize(height); for (int y = 0; y < height; ++y) { maze[y].resize(width); for (int x = 0; x < width; ++x) { maze[y][x].x = x; maze[y][x].y = y; } } std::srand(std::time(nullptr)); }随机DFS核心实现
void generateMaze(std::vector<std::vector<Cell>>& maze) { std::stack<Cell*> cellStack; Cell* current = &maze[0][0]; current->visited = true; cellStack.push(current); while (!cellStack.empty()) { current = cellStack.top(); auto neighbors = getUnvisitedNeighbors(current, maze); if (!neighbors.empty()) { Cell* next = neighbors[std::rand() % neighbors.size()]; removeWalls(current, next); next->visited = true; cellStack.push(next); } else { cellStack.pop(); } } }辅助函数实现
std::vector<Cell*> getUnvisitedNeighbors(Cell* cell, const std::vector<std::vector<Cell>>& maze) { std::vector<Cell*> neighbors; int dx[] = {0, 1, 0, -1}; int dy[] = {-1, 0, 1, 0}; for (int i = 0; i < 4; ++i) { int nx = cell->x + dx[i]; int ny = cell->y + dy[i]; if (nx >= 0 && nx < maze[0].size() && ny >= 0 && ny < maze.size() && !maze[ny][nx].visited) { neighbors.push_back(const_cast<Cell*>(&maze[ny][nx])); } } return neighbors; } void removeWalls(Cell* a, Cell* b) { if (a->x == b->x) { if (a->y < b->y) { a->bottom_wall = false; b->top_wall = false; } else { a->top_wall = false; b->bottom_wall = false; } } else { if (a->x < b->x) { a->right_wall = false; b->left_wall = false; } else { a->left_wall = false; b->right_wall = false; } } }迷宫求解实现
路径搜索算法
bool solveMaze(std::vector<std::vector<Cell>>& maze, Cell* start, Cell* end, std::vector<Cell*>& path) { std::stack<Cell*> stack; stack.push(start); start->visited = true; while (!stack.empty()) { Cell* current = stack.top(); path.push_back(current); if (current == end) return true; auto neighbors = getAccessibleNeighbors(current, maze); if (!neighbors.empty()) { Cell* next = neighbors[std::rand() % neighbors.size()]; next->visited = true; stack.push(next); } else { path.pop_back(); stack.pop(); } } return false; }可通行邻居检测
std::vector<Cell*> getAccessibleNeighbors(Cell* cell, const std::vector<std::vector<Cell>>& maze) { std::vector<Cell*> neighbors; int dx[] = {0, 1, 0, -1}; int dy[] = {-1, 0, 1, 0}; bool walls[] = {cell->top_wall, cell->right_wall, cell->bottom_wall, cell->left_wall}; for (int i = 0; i < 4; ++i) { if (!walls[i]) { int nx = cell->x + dx[i]; int ny = cell->y + dy[i]; if (nx >= 0 && nx < maze[0].size() && ny >= 0 && ny < maze.size() && !maze[ny][nx].visited) { neighbors.push_back(const_cast<Cell*>(&maze[ny][nx])); } } } return neighbors; }可视化输出
控制台打印迷宫
void printMaze(const std::vector<std::vector<Cell>>& maze) { for (const auto& row : maze) { // 打印顶部墙壁 for (const auto& cell : row) { std::cout << (cell.top_wall ? "+---" : "+ "); } std::cout << "+\n"; // 打印侧边墙壁 for (const auto& cell : row) { std::cout << (cell.left_wall ? "|" : " "); std::cout << " "; } std::cout << "|\n"; } // 打印底部边界 for (size_t i = 0; i < maze[0].size(); ++i) { std::cout << "+---"; } std::cout << "+\n"; }完整示例调用
int main() { const int WIDTH = 10, HEIGHT = 10; std::vector<std::vector<Cell>> maze; initMaze(maze, WIDTH, HEIGHT); generateMaze(maze); std::vector<Cell*> path; solveMaze(maze, &maze[0][0], &maze[HEIGHT-1][WIDTH-1], path); printMaze(maze); return 0; }算法优化方向
- 记忆化搜索：记录已探索路径避免重复计算
- 双向搜索：从起点和终点同时进行搜索
- 启发式引导：结合曼哈顿距离等启发式信息
- 并行化处理：利用多线程加速搜索过程
该实现完整展示了随机DFS在迷宫生成与求解中的应用，通过随机选择邻接节点使得每次生成的迷宫都具有独特性，同时保持算法的高效性。
