devbox
我家小花儿
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

深度优先搜索详解

作者：我家小花儿 | 2024-04-26 19:20:14

赞

踩

深度优先搜索

目录

前言

一、工作原理

二、模板

函数模板：

准备工作

三、主要应用

（一）寻找全部路径

题目描述

输入格式

输出格式

样例输入

样例输出

参考代码

思路

原题链接：1213: 走迷宫

（二）统计连通块数量

题目描述

样例输入

样例输出

参考代码

思路

原题链接：P1596 [USACO10OCT] Lake Counting S​​​​​

四、易错点总结

（一）方向数组

（二）一定要回溯！

（三）进行多轮判断（详见走迷宫参考代码）

前言

深度优先搜索，简称“深搜”，DFS，主要用于无向无权简单图的搜索工作，与广度优先搜索并称两大优先搜索算法，可以使用栈，也可以递归实现，数据量大用栈，小就用递归。

一、工作原理

深度优先搜索（DFS）是一种用于遍历或搜索树或图的算法，它从根节点或起始节点开始，首先访问所有可到达的节点，然后对于每个可到达的节点，再递归地访问其未访问过的相邻节点，直到所有节点都被访问为止。

我们来仔细地看一下这个过程：

 

 

 

 

 

深度优先搜素大致可以这样描述：不撞南墙不回头，它沿着一条路一直走下去，直到走不动了然后返回上一个岔路口选择另一条路继续前进，一直如此，直到走完所有能够到达的地方！它的名字中深度两个字其实就说明了一切，每一次遍历都是走到最深！

注意一个细节：在我们上面的最后一个图中，顶点3仍然未被标记（绿色）。我们可以得到以下结论：

使用深度优先搜索遍历一个图，我们可以遍历的范围是所有和起点连通的部分，通过这一个结论，下文我们可以实现一个判断整个图连通性的方法。

二、模板

函数模板：

  1. void dfs(int x, int y)
  2. {
  3. 	if(出口)
  4. 	{
  5. 		退出或特殊操作
  6. 	}
  7. 	
  8. 	
  9. 	标记
  10.  
  11. 	for(主要是遍历所有方向 4、8...)
  12. 	{
  13. 		nx = x + dx[i]; //确定下一步的位置
  14. 		ny = y + dy[i]; 
  15. 		
  16. 		if(nx >= 0 && nx < n && ny >= 0 && ny < m && —特殊判断—)//判断下一步的位置是否合法？
  17. 		{
  18. 			标记数组为true
  19. 			dfs(nx, ny); //递归
  20.             标记数组为false//递归结束回溯，不然会影响下一层递归的结果
  21. 		}
  22. 	}
  23. }

准备工作

  1. int a[105][105]; //原数组
  2. int dx[9] = {0, -1, 1, 0, 0, -1, -1, 1, 1}; //方向数组
  3. int dy[9] = {0, 0, 0, -1, 1, -1, 1, -1, 1};
  4. int vis[105][105]; //标记访问数组
  5. int n, m; //其他变量

三、主要应用

（一）寻找全部路径

我们通过深度优先搜索可以轻松地遍历一个图，如果我们在此基础上增加一些代码就可以很方便地查找图中的路径！

比如，题目给定顶点A和顶点B,让你求得从A能不能到达B？如果能，给出一个可行的路径！

据一道例题来说明一下：

题目描述

有一个n*m格的迷宫(表示有n行、m列)，其中有可走的也有不可走的，如果用1表示可以走，0表示不可以走，文件读入这n*m个数据和起始点、结束点(起始点和结束点都是用两个数据来描述的，分别表示这个点的行号和列号)。现在要你编程找出所有可行的道路，要求所走的路中没有重复的点，走时只能是上下左右四个方向。如果一条路都不可行，则输出相应信息(用-1表示无路)。

请统一用 左上右下的顺序拓展，也就是 (0,-1),(-1,0),(0,1),(1,0)。

输入格式

第一行是两个数n，m( 1 < n ， m < 15 )，接下来是n行m列由1和0组成的数据，最后两行是起始点和结束点。

输出格式

所有可行的路径，描述一个点时用(x，y)的形式，除开始点外，其他的都要用“->”表示方向。

如果没有一条可行的路则输出-1。

样例输入

  1. 5 6
  2. 1 0 0 1 0 1
  3. 1 1 1 1 1 1
  4. 0 0 1 1 1 0
  5. 1 1 1 1 1 0
  6. 1 1 1 0 1 1
  7. 1 1
  8. 5 6

样例输出

  1. (1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(3,4)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)
  2. (1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)
  3. (1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)
  4. (1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)
  5. (1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)
  6. (1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)
  7. (1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)
  8. (1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)
  9. (1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)
  10. (1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(3,4)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)
  11. (1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)
  12. (1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)

参考代码

思路

这里呢，我先用vector存储每一步的路径，因为在运行时你是不确定它是否可以到达终点的，所以每一步都要存储，二维坐标系（x， y）所以需要结构体 node 搭配 vector十分的完美，print函数有一个细节大家要注意一下，在样例输入中，我们可以发现在每一条路径的结尾是没有箭头“->”的，所以要有一个小 if 判断一下，不然很有可能爆0的哦！

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <cstring>
  5. #define ll long long
  6. using namespace std;
  7.  
  8. struct node
  9. {
  10. 	int x;
  11. 	int y;
  12. };
  13. vector <node> v;
  14. int a[20][20], sx, sy, ex, ey, n, m;
  15. int dx[5] = {0, 0, -1, 0, 1};
  16. int dy[5] = {0, -1, 0, 1, 0};
  17. bool vis[20][20], vflag = false, flag = false;
  18.  
  19. void print()
  20. {
  21. 	for(vector<node>::iterator iter = v.begin(); iter != v.end(); iter++)
  22. 	{
  23. 		if(iter + 1 == v.end())
  24. 			cout<<"("<<iter->x<<","<<iter->y<<")";
  25. 		else
  26. 			cout<<"("<<iter->x<<","<<iter->y<<")"<<"->";
  27. 	}
  28. }
  29.  
  30. void dfs(int x, int y)
  31. {
  32. 	vis[x][y] = true;
  33. 	node tmp;
  34. 	tmp.x = x;
  35. 	tmp.y = y;
  36. 	v.push_back(tmp);
  37. 	
  38. 	if(x == ex && y == ey)
  39. 	{
  40. 		flag = true;
  41. 		print();
  42. 		cout<<endl;
  43. 		v.clear();
  44. 		node tmp;
  45. 		tmp.x = sx;
  46. 		tmp.y = sy;
  47. 		v.push_back(tmp);
  48. 		
  49. 		return ;
  50. 	}
  51. 	
  52. 	for(int i = 1; i <= 4; i++)
  53. 	{
  54. 		int nx = x + dx[i];
  55. 		int ny = y + dy[i];
  56. 		
  57. 		if(nx >= 1 && nx <= n && ny >= 1 && ny <= m && !vis[nx][ny] && a[nx][ny] == 1)
  58. 		{	
  59. 			vis[nx][ny] = true;
  60. 			dfs(nx, ny);
  61.  
  62. 			vis[nx][ny] = false;
  63. 			for(vector<node>::iterator iter = v.begin(); iter != v.end(); )
  64. 			{
  65. 				if(iter->x == tmp.x && iter->y == tmp.y)
  66. 					iter = v.erase(iter);
  67. 				else
  68. 					iter++;
  69. 			}
  70. 		}
  71. 	}
  72. }
  73.  
  74. int main()
  75. {
  76. 	cin>>n>>m;
  77. 	
  78. 	for(int i = 1; i <= n; i++)
  79. 	{
  80. 		for(int j = 1; j <= m; j++)
  81. 		{
  82. 			cin>>a[i][j];
  83. 		}
  84. 	}
  85. 	
  86. 	cin>>sx>>sy;
  87. 	cin>>ex>>ey;
  88. 	
  89. 	dfs(sx, sy);
  90. 	
  91. 	if(!flag)
  92. 	{
  93. 		cout<<"-1"<<endl;
  94. 		return 0;
  95. 	}
  96. 	
  97. 	return 0;
  98. }

原题链接：1213: 走迷宫

感兴趣的伙伴可以去做一做，还是比较简单的！

（二）统计连通块数量

还记得我们上文讲到的dfs的一条性质吗？一个dfs搜索能够遍历与起点相连通的所有顶点。我们可以这样思考：申请一个整型数组id[0]用来将顶点分类——“联通的顶点的id相同，不连通的顶点的id不同”。首先，我对顶点adj[0]进行dfs，把所有能够遍历到的顶点的id设置为0，然后把这些顶点都标记；接下来对所有没有被标记的顶点进行dfs，执行同样的操作，比如将id设为1，这样依次类推，直到把所有的顶点标记。最后我们我们得到的id[]就可以完整的反映这个图的连通情况。

我们再举例一道题来说明一下：

题目描述

由于近期的降雨，雨水汇集在农民约翰的田地不同的地方。我们用一个 N×M (1 ≤ N ≤ 100,1 ≤ M ≤ 100) 的网格图表示。每个网格中有水（W） 或是旱地（.）。一个网格与其周围的八个网格相连，而一组相连的网格视为一个水坑。约翰想弄清楚他的田地已经形成了多少水坑。给出约翰田地的示意图，确定当中有多少水坑。

输入第 11 行：两个空格隔开的整数：N 和 M。

第 22 行到第 N+1 行：每行 M 个字符，每个字符是 W 或 .，它们表示网格图中的一排。字符之间没有空格。

输出一行，表示水坑的数量。

样例输入

  1. 10 12
  2. W........WW.
  3. .WWW.....WWW
  4. ....WW...WW.
  5. .........WW.
  6. .........W..
  7. ..W......W..
  8. .W.W.....WW.
  9. W.W.W.....W.
  10. .W.W......W.
  11. ..W.......W.

样例输出

3

参考代码

思路

这次是8方向遍历所以 dx 和 dy 数组需要更改，仍然还是模板直接往上套，我省去了vis标记数组，因为我们只需要把原数组s的坐标是水的位置一遍历到就改成空地，就简单轻松的做到了vis数组的全部功能。 

  1. #include <iostream>
  2. #include <cstdio>
  3. #define ll long long
  4. using namespace std;
  5.  
  6. char s[105][105];
  7. int dx[9] = {0, -1, 1, 0, 0, -1, -1, 1, 1};
  8. int dy[9] = {0, 0, 0, -1, 1, -1, 1, -1, 1};
  9. int n, m, ans = 0;
  10. bool flag = false;
  11.  
  12. void dfs(int x, int y)
  13. {
  14. 	if(s[x][y] == 'W')
  15. 	{
  16. 		flag = true;
  17. 	}
  18. 	
  19. 	
  20. 	s[x][y] = '.';
  21. 	int nx, ny;
  22. 	for(int i = 1; i <= 8; i++)
  23. 	{
  24. 		nx = x + dx[i];
  25. 		ny = y + dy[i];
  26. 		
  27. 		if((nx >= 0 && nx < n && ny >= 0 && ny < m) && s[nx][ny] == 'W')
  28. 		{
  29. 			flag = true;
  30. 			dfs(nx, ny);
  31. 		}
  32. 	}
  33.  
  34. }
  35.  
  36. int main()
  37. {
  38. 	scanf("%d%d", &n, &m);
  39. 	 
  40. 	
  41. 	for(int i = 0; i < n; i++)
  42. 	{
  43. 		for(int j = 0; j < m; j++)
  44. 		{
  45. 			cin>>s[i][j];
  46. 		}
  47. 	}
  48. 	
  49. 	for(int i = 0; i < n; i++)
  50. 	{
  51. 		for(int j = 0; j < m; j++)
  52. 		{
  53. 			dfs(i, j);
  54.  
  55. 			if (flag)
  56. 			{
  57. 				ans++;
  58. 				flag = false;
  59. 			}			
  60. 		}
  61. 	}
  62. 	
  63. 	cout<<ans;
  64. 	return 0;
  65. }

原题链接：P1596 [USACO10OCT] Lake Counting S​​​​​

四、易错点总结

（一）方向数组

方向数组一定要写对，不然全盘乱透

  1. //4方向，这里我是按照上、下、左、右的顺序进行的排列
  2. int dx[5] = {0, -1, 1, 0, 0};
  3. int dy[5] = {0, 0, 0, -1, 1};
  4. //8方向，这里我是按照上、下、左、右、左上、右上、左下、右下的顺序进行的排列
  5. int dx[9] = {0, -1, 1, 0, 0, -1, -1, 1, 1};
  6. int dx[9] = {0, 0, 0, -1, 1, -1, 1, -1, 1};
  7. //这里因为我是从1开始存储数组的，所以第一个要多垫一个0，记性好的老铁可以从0开始，但千万不要搞混！

（二）一定要回溯！

除非题目已经要求每个坐标只能走一次，不然DFS一定要加回溯！！

  1. vis[nx][ny] = true;
  2. dfs(nx, ny);
  3. vis[nx][ny] = false; //回溯！！

假设第 i 轮你走完了，到第 i + 1轮的时候如果你不把vis[nx][ny]的true设为false的话等于你到第 i + 1轮还留着第 i 轮的标记，就会出现重大错误！！

（三）进行多轮判断（详见走迷宫参考代码）

走迷宫这道题就是要找到所有的路径，所以记录路径的 v 就需要每次 clear() 一遍防止这一轮还留着上一轮的路径。

代码片段

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家小花儿/article/detail/492721
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。