我要评论dfs算法
by.qin3yu
栈相关操作可以参考我的往期博文：
【c++数据结构 | 栈速通】使用栈完成十进制数转二四八进制数.by.qin3yu
文中所有代码使用 c++ 举例，且默认已使用std命名空间：
using namespace std;
概念速览
什么是dfs算法？
- dfs，即深度优先搜索（depth-first search）是一种常用的图遍历算法。它通过从起始节点开始，沿着一条路径尽可能深地探索图的节点，直到达到不能继续前进的叶子节点，然后回溯到前一个节点继续探索其他路径，如下图所示：
图中黑色代表迷宫的墙体（障碍）；白色代表通道；绿色越深，代表搜索的顺序越靠前；灰色代表被回溯的路径。
- dfs 的特点是优先探索深度而不是广度。它会尽可能深地搜索每一个路径，直到找到目标节点或者遍历完所有节点。通过使用栈来保存遍历过程中的节点。
什么是bfs算法？
- 与深度优先搜索相反，bfs采用的是广度优先搜索，他的基本思想是像细菌扩张一样，从终点向外逐层扩张，直到找到终点或将全图遍历一遍。
关于bfs算法的详细解释可以参考我的往期博文，本文将不作赘述：
【c++数据结构 | 队列速通】图解bfs算法走迷宫最短路径问题.by.qin3yu
dfs的优势与劣势
- dfs与同作为图算法的bfs相比，具有以下特点：
在实际应用中，我们通常需要求出最优（最短）路径，且我们不能保证地图中没有环状路径，因此我们通常认为：在绝大部分情况下bfs比dfs更优。
dfs算法详解
初始化迷宫地图
-
既然要走迷宫，那么就要先有迷宫地图。在本题中，题目要求使用10×10规格的地图，但此处为了便于讲解，我们使用4×4规格的地图，原理都是相同的。若要改为10×10规格，改变对应变量即可（详见结尾代码）。
-
在上面的地图中，每个格子代表一个点，用对应的字母表示，a为起点，p为终点，白色代表可通行路径，黑色代表障碍物。
-
如何用代码实现以上地图结构？遵循搜索算法五要素：
1. 遍历范围
int maze[4][4] = {
{0, 1, 0, 0},
{0, 0, 0, 1},
{1, 0, 1, 1},
{0, 0, 0, 0},};
2. 父结点
// 定义节点结构体
struct node
{
int x;
int y;
int parent; // 记录父节点在栈中的索引
};
如图所示，访问点 a 后要访问点 b ，所以 a 为 b 的父结点
3. 初始点和目标点
node start = { 0, 0, -1}; // 设置起点
node end = { 3, 3, -1}; // 设置终点
// 终点和起点没有父结点，所以设置父结点索引为-1
4. 搜索方向
// 用二维数组表示方向，分别对应上下左右四个方向，后文称为方向数组
int directions[4][2] = { { -1, 0}, { 0, 1}, { 1, 0}, { 0, -1} };
5. 访问标记
// 用二维数组记录是否访问，地图上的每个点都对应一个bool值
bool visited[4][4] = { false };
算法结构
- 在走迷宫时，我们需要在搜索路径前先判断是否已经到终点，若不是则继续搜索，直到搜索到死胡同里，我们在回头至上一个岔路口，因此整体的算法结构如下：
while (bool){
// 终点处理
// 结点访问
// 路径回溯
}
但下文为了使读者便于理解，不会根据此顺序讲解，读者只需知道三个部分的先后顺序即可。
访问结点
- 访问结点包含以下几个步骤：
- 在下面的代码中，我们还要考虑一个额外因素：如何知道所有可能的路径都被访问过？
- 对此，我们用以下方法解决：
因为后文需要做路径回溯的处理，所以拥有先进后出特性的 栈 最适合用于存放路径，具体代码示例如下：
bool has_unvisited = false; // 定义布尔型变量，标记是否还有未访问的节点
for (int i = 0; i < 4; i++) // 枚举上、右、下、左四个方向
{
int next_x = current.x + directions[i][0];
int next_y = current.y + directions[i][1];
if (next_x >= 0 && next_x < 4 && next_y >= 0 && next_y < 4
&& maze[next_x][next_y] == 0 && !visited[next_x][next_y]) // 判断是否是合法的下一个节点
{
node next_node = { next_x, next_y, path.size() }; // 创建下一个节点
visited[next_x][next_y] = true; // 标记下一个节点为已访问
path.push(next_node); // 将下一个节点入栈
has_unvisited = true; // 更新变量
break;
}
}
路径回溯
- 在上文中，我们使用栈来保存路径，根据栈先进后出的特性，我们回溯路径只需把最后一步弹出即可：
- 如上图所示，我们走到“死胡同” e 点以后，开始将栈中的路径弹出，一直弹出至当前点还有未访问的相邻点则停止回溯，继续访问此未访问的结点，代码如下：
if (!has_unvisited) // 如果没有未访问的节点，就弹出当前节点
{
path.pop();
}
终点处理
打印路径
- 根据上文所述，如果当前点回溯到了起始点，即栈为空，则代表已经遍历过全图，无法找到搜索到终点：
while (!path.empty()){
// 终点处理
// 结点访问
// 路径回溯
}
cout << "未找到可行路径！" << endl;
- 另一种可能，如果当前点的坐标等于终点的坐标，则代表已经找到终点，我们只需要将路径回溯打印出即可，具体操作为将栈内元素逐个打印并弹出，原理如下图所示：
- 从图中可以看出，根据先进后出的原则，栈内元素被逐个打印后获得的路线应该是从终点到起点的路线：
node current = path.top(); // 取出栈顶节点
if (current.x == end.x && current.y == end.y) // 如果找到终点，就输出路径
{
cout << "路径如下：" << endl;
while (!path.empty())
{
node node = path.top();
cout << "(" << node.x << "," << node.y << ") ";
path.pop();
}
cout << endl;
return;
}
- 如果您不在乎路线的正反，则到这里全文就结束了。
反转路径
- 如果想将顺序颠倒过来，变成从起点到终点的路径，我们也可以用通过使用一个辅助栈来实现，原理如下图所示：
具体实现如下：
if (current.x == end.x && current.y == end.y) // 如果找到终点，就输出路径
{
cout << "路径如下：" << endl;
stack<node> reversepath; // 声明一个辅助栈，用来保存反转后的顺序
while (!path.empty())
{
reversepath.push(path.top());
path.pop();
}
while (!reversepath.empty()) // 打印辅助栈中的内容
{
node node = reversepath.top();
cout << "( " << node.x << " , " << node.y << " ) ";
reversepath.pop();
}
cout << endl;
return;
}
至此，dfs算法讲解完毕（=
完整项目代码
如需提问，可以在评论需留言或私信，通常在12小时内回复。不收费，用爱发电（=
#include <iostream>
#include <stack>
using namespace std;
// 定义迷宫地图，0 表示可以通行，1 表示障碍物
int maze[10][10] = {
{0, 0, 1, 0, 0, 0, 1, 0, 1, 0},
{0, 0, 1, 0, 0, 0, 0, 0, 1, 0},
{0, 0, 0, 0, 1, 1, 0, 1, 1, 0},
{0, 1, 1, 1, 0, 0, 0, 1, 0, 0},
{0, 0, 0, 1, 0, 0, 0, 0, 0, 0},
{0, 1, 0, 0, 0, 1, 0, 1, 1, 0},
{0, 1, 1, 1, 1, 0, 0, 1, 1, 0},
{0, 1, 0, 0, 0, 0, 1, 0, 0, 0},
{0, 0, 0, 1, 1, 0, 1, 0, 1, 0},
{0, 1, 1, 1, 0, 0, 0, 0, 1, 0}
};
// 定义方向数组，顺序为上、右、下、左
int directions[4][2] = { {-1,0}, {0,1}, {1,0}, {0,-1} };
// 定义节点结构体
struct node{
int x;
int y;
int parent; // 记录父节点在栈中的索引
};
// 定义寻找最短路线的函数
void dfs(node start, node end){
bool visited[10][10] = { false }; // 定义记录访问过节点的布尔型数组
stack<node> path; // 定义保存路径的栈
path.push(start); // 将起点入栈
visited[start.x][start.y] = true; // 将起点标记为已访问
while (!path.empty()){
node current = path.top(); // 取出栈顶节点
if (current.x == end.x && current.y == end.y){ // 如果找到终点，就输出路径
cout << "路径如下：" << endl;
stack<node> reversepath; // 声明一个辅助栈，用来保存反转后的顺序
while (!path.empty()){
reversepath.push(path.top());
path.pop();
}
while (!reversepath.empty()){ // 打印辅助栈中的内容
node node = reversepath.top();
cout << "( " << node.x << " , " << node.y << " ) ";
reversepath.pop();
}
cout << endl;
return;
}
bool has_unvisited = false; // 定义布尔型变量，标记是否还有未访问的节点
for (int i = 0; i < 4; i++){ // 枚举上、右、下、左四个方向
int next_x = current.x + directions[i][0];
int next_y = current.y + directions[i][1];
if (next_x >= 0 && next_x < 10 && next_y >= 0 && next_y < 10
&& maze[next_x][next_y] == 0 && !visited[next_x][next_y]){ // 判断是否是合法的下一个节点
node next_node = { next_x, next_y, path.size() }; // 创建下一个节点
visited[next_x][next_y] = true; // 标记下一个节点为已访问
path.push(next_node); // 将下一个节点入栈
has_unvisited = true; // 更新变量
break;
}
}
if (!has_unvisited){ // 如果没有未访问的节点，就弹出当前节点
path.pop();
}
}
cout << "未找到可行路径！" << endl;
}
int main(){
node start = { 0,0,-1 }; // 设置起点
node end = { 9,9,-1 }; // 设置终点
dfs(start, end); // 调用深度优先搜索函数
system("pause");
return 0;
}
发表评论