DFS的介绍
DFS（深度优先搜索，Depth-First Search）是一种用于遍历或搜索树或图的算法。
它从一个节点开始，尽可能深地搜索树的分支，直到到达叶子节点（没有子节点的节点），然后回溯到上一个节点，继续搜索其他分支。
这个过程会一直进行，直到所有可能的分支都被探索完毕。
工作原理
DFS的工作原理可以总结为以下几个步骤
- 选择一个起始节点：从树或图的某个节点开始。
- 探索尽可能深的分支：从当前节点开始，选择一个未被访问过的邻接节点，然后递归地在该节点上执行DFS。
- 回溯：当当前节点的所有邻接节点都被访问过，或者到达了叶子节点时，回溯到上一个节点。
- 重复：重复步骤2和3，直到所有节点都被访问过。
DFS的特点
- 栈的使用：在实现DFS时，通常使用栈数据结构来存储节点。在递归实现中，调用栈隐式地充当了栈的角色。
- 时间复杂度：对于有V个顶点和E条边的图，DFS的时间复杂度通常是O(V + E)。
- 空间复杂度：在最坏的情况下，DFS的空间复杂度也是O(V)，因为可能需要存储整个路径上的节点。
- 路径搜索：DFS非常适合于寻找从起点到终点的路径，尤其是在图不是非常大的情况下。
- 连通性问题：DFS可以用来检测图的连通性，例如，检查一个图是否是强连通的。
图示示例
下面是一个简单的图示：
节点1为根节点，也叫起始节点
那么节点1向下遍历，直到遍历到第一个没有子节点的节点4
因为4已经没有子节点，已经是叶子节点，所以无法再向下遍历，所以回溯到上一个它的父节点3，并对节点4作标记，节点3接着向下遍历未被标记的子节点5
因为5同样是叶子节点，遍历有到达了最深层，所以继续回溯到父节点3，同时标记5，我们发现3也没有未被标记的子节点了，无法再向下遍历，那么3接着向上回溯到父节点2，同时对3作标记，继续遍历2的未被标记的子节点6
接下来过程：2→6→7，节点7向上回溯到6并标记,节点6向下遍历子节点:6→8,然后连续向上回溯 8→6→2→1 直到回溯到根节点1,发现有可以向下遍历的子节点
接着按照上述模式进行剩余的遍历，完成整张图的遍历，图的序号即为遍历的顺序
例题：马的遍历
这是Luogu上一道搜索的例题 https://www.luogu.com.cn/problem/P1443
接着给出示例代码
1
2
3
4
5
6
7
8
9
| #include<bits/stdc++.h>
using namespace std;
const int MAXN = 1000009;
bool is[401][401];
int num[401][401];
int n,m,begin_x,begin_y;
int move_x[8] = {1,1,2,2,-1,-1,-2,-2};
int move_y[8] = {2,-2,1,-1,2,-2,1,-1};
|
初始工作
1
2
3
4
5
6
7
8
9
| int main(){
cin>>n>>m>>begin_x>>begin_y;
memset(is,true,sizeof(is));
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++) num[i][j] = MAXN;
dfs(begin_x,begin_y,0);
print();
return 0;
}
|
main函数的内容如上，初始化标记数组is,为全部未访问过，num[i][j]初始化为一个极大的数
dfs(int x,int y,int k)为一个递归函数 x,y:当前点位的横坐标; k:走到目前点位的步数
dfs(begin_x,begin_y,0) 即从初始点位开始dfs，步数为0（马到起始点的步数为0）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| void dfs(int x,int y,int k)
{
if(x <= 0||y <= 0||num[x][y] < k||x > n || y > m) return;
num[x][y] = k;
for(int i = 0 ;i < 8; i++)
{
int tx = move_x[i] + x;
int ty = move_y[i] + y;
is[x][y] = false;
dfs(tx,ty,k + 1);
is[x][y] = true;
}
}
|
dfs内容如上
接着我们需要对题目所要求的输出进行修改，有格式要求
1
2
3
4
5
6
7
8
9
10
11
12
| void print()
{
for(int i = 1 ; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
if(num[i][j] == MAXN) cout<<"-1 ";
else cout<<num[i][j]<<" ";
}
cout<<endl;
}
}
|
当然你也可以采取下面修改场宽的方式进行所要求格式的输出
1
| printf("%-5d",num[i][j]);
|
全部代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| #include<bits/stdc++.h>
using namespace std;
const int MAXN = 1000009;
bool is[401][401];
int num[401][401];
int n,m,begin_x,begin_y;
int move_x[8] = {1,1,2,2,-1,-1,-2,-2};
int move_y[8] = {2,-2,1,-1,2,-2,1,-1};
void dfs(int x,int y,int k)
{
if(x <= 0||y <= 0||num[x][y] < k||x > n || y > m) return;
num[x][y] = k;
for(int i = 0 ;i < 8; i++)
{
int tx = move_x[i] + x;
int ty = move_y[i] + y;
is[x][y] = false;
dfs(tx,ty,k + 1);
is[x][y] = true;
}
}
void print()
{
for(int i = 1 ; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
if(num[i][j] == MAXN) cout<<"-1 ";
else cout<<num[i][j]<<" ";
}
cout<<endl;
}
}
int main(){
cin>>n>>m>>begin_x>>begin_y;
memset(is,true,sizeof(is));
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++) num[i][j] = MAXN;
dfs(begin_x,begin_y,0);
print();
return 0;
}
|
在代码中，DFS被用来计算从起点开始，到达每个位置所需的最少移动次数。虽然最终结果可能是正确的，但由于DFS的递归性质，它可能会导致大量的函数调用开销，并且可能会在没有找到更优解的情况下继续深入搜索，从而导致效率较低。
接下来 将引入在这个场景下更为合适的另一种搜索方法，宽（广）度优先搜索（BFS）
