DFS和BFS理解+模板+例题

DFS（深度优先搜索）

本质上是暴力把所有的路径都搜索出来，它运用了回溯，保存这次的位置并深入搜索，都搜索完便回溯回来，搜下一个位置，直到把所有最深位置都搜一遍（找到目的解返回或者全部遍历完返回一个事先定好的值）。要注意的一点是，搜索的时候有记录走过的位置，标记完后可能要改回来。
dfs一般借用递归完成整个算法的构造。

int dfs()
{
    if(达到目的)处理return;
    else
    {
        处理;
        dfs();
    }
}

dfs：1-2-5，5不能再走了，退回到2，走6，退回2退回1，到3，以此类推。

例题、力扣：

解法1（经典dfs）

class Solution {
public:
    vector<int> pondSizes(vector<vector<int>>& land) {
        
        vector<int> res;
        for(int i = 0; i < land.size(); i++){
            for(int j = 0; j < land[0].size(); j++){
                int count = 0;
                if(land[i][j] == 0){
                    dfs(i, j, land, count);
                    if(count != 0)
                        res.push_back(count);
                }
            }
        }
        sort(res.begin(), res.end());
        return res;
 
    }
 
    void dfs(int x, int y, vector<vector<int>> &land, int &count){
        land[x][y] = -1;
        count++;
        int dirx[8] = {0,0,1,1,1,-1,-1,-1};
        int diry[8] = {1,-1,1,-1,0,1,-1,0};
        for(int i = 0; i < 8; i++){
            int x1 = x + dirx[i];
            int y1 = y + diry[i];
            if(x1 >= 0 && x1 < land.size() && y1 >= 0 && y1 < land[0].size() && land[x1][y1] == 0){
                dfs(x1, y1, land, count);
            }
        }
    }
 
};

BFS（广度优先搜索）

bfs也是一个对连通图进行遍历的算法。它的思想是从一个被选定的点出发；然后从这个点的所有方向每次只走一步的走到底（即其中一个方向走完一步之后换下一个方向继续走）；如果得不到目的解，那就返回事先定好的值，如果找到直接返回目的解。
与dfs不同的是，bfs不是运用的递归，而是运用队列和函数内循环构造的。

int visit[N][N]//用来记录走过的位置
int dir[4][2]={0,-1,0,1,-1,0,1,0};
struct node
{
	int x,y,bits;//一般是点，还有步数，也可以存其他的
};
queue<node>v;
void bfs1(node p)
{
	node t,tt;
	v.push(p);
	while(!v.empty())
	{
		t=v.front();//取出最前面的
		v.pop();//删除
		if(找到符合条件的)
		{
			做记录；
			while(!v.empty()) v.pop();//如果后面还需要用，随手清空队列
			return;
		}
		visit[t.x][t.y]=1;//走过的进行标记，以免重复
		rep(i,0,4)//做多次查找
		{
			tt=t;
			tt.x+=dir[i][0];tt.y+=dir[i][1];//这里的例子是向上下左右查找的
			if(如果这个位置符合条件)
			{
				tt.bits++;//步数加一
				v.push(tt); //把它推入队列，在后面的时候就可以用了
			}
		}
	}
}

R语言：rep函数解析
（其实就是for(i=0;i<4;i++)吧...）

bfs：从1开始搜，有2，3，4几个点，存起来，从2开始有5，6，存起来，搜3，有7，8，存起来，搜4，没有了；现在开始搜刚刚存的点，从5开始，没有，然后搜6.。。一直进行，直到找到；

二者区别&例子

DFS：使用栈保存未被检测的结点，结点按照深度优先的次序被访问并依次被压入栈中，并以相反的次序出栈进行新的检测。
——类似于树的先根遍历
——深搜例子：走迷宫，你没有办法用分身术来站在每个走过的位置。不撞南山不回头。

BFS：使用队列保存未被检测的结点。结点按照宽度优先的次序被访问和进出队列。
——类似于树的按层次遍历的过程
——广搜例子：你的眼镜掉到地上以后，你趴在地板上找。你总是先摸最接近你的地方，如果没有，再摸远一点的地方......

BFS用来搜索最短路径的解法是比较合适的。
比如求最少步数的解，最少交换次数的解，最快走出迷宫等等，因为bfs搜索过程中遇到的第一个解一定是离最初位置最近的，所以遇到第一个解，一定就是最优解，此时搜索算法可以终止。
而如果用dfs，会搜一些其他的位置，需要花相对比较多的时间，需要搜很多次，然后如果找到还不一定是最优解，还要记录这次找的位置，与之后找到的答案进行比较，看看谁才是最优解，这样就比较麻烦。

DFS用来搜索全部的解。
在记录路径的时候会简单一点，只需要把每一次找的点，放进去答案中就好；并且，相对而言dfs在做很多题目可以用上，比如分治、数位dp，其实就是递归，而dfs用的就比较少。

BFS是浪费空间节省时间，DFS是浪费时间节省空间。
因为dfs要走很多的路径，可能都是没用的。（做有些题目的时候要进行剪枝，就是确定不符合条件的就可以结束，以免浪费时间，否则有些题目会TLE）
而bfs可以走的点要存起来，需要队列，因此需要空间来储存，便是浪费了空间，假设有十层，各个结点有2个子节点，那么储存到第10层就要存2^10-1个数据，而dfs只需要存10个数据，但是找到答案的速度相对快一点。

当遇到一些层次较深的树图时，dfs一读到底的风格就不太适合一些限制时间的题，因为针对这些内存巨大的，使用dfs就会比较耗时，比方说一个数有1000个树枝，每个树枝有100个子叶，第1000的第一颗叶子就是正解，但是在遍历的时候却选择从第一个树枝开始遍历且一读到底，遍历到正解得时候已经做了999*100次遍历了，这时只要把dfs换成bfs，就会节约许多时间，只需要1000次的遍历就可以找到答案，所以由上可得，在一些大的内存或者层次比较的大树，应选择使用bfs来解决；反之，则使用dfs。

还有一些根据题意就可以看出来是选择dfs还是bfs；比如题中需要的目的解是需要判断从最初的状态能否得到，这个时候就应该选择dfs了。像一些需要一步一步的完成就要选择bfs。

总的来说，dfs和bfs大都运用在图的处理上：如迷宫，八皇后，n皇后，油田，连通块，数独等，在这些类型的题上几乎全需要dfs或bfs来解，或者说有些难度更大的需要bfs+dfs或bfs+bfs才能完成。