深度优先搜索（dfs）和广度优先搜索（bfs）

目录

一、前言

二、关于dfs和bfs有意思的小故事

三、深搜题例

1、小猫爬山链接

2、基本思路

3、代码

（1）python代码

四、广搜题例

1、武士风度的牛链接

2、基本思路

3、代码

（1）C++代码

（3）python代码

---

一、前言

对于学计算机的同学来说，学习算法是一件非常重要的事情，废话不多讲，我们来讲讲“dfs和bfs问题”。

二、关于dfs和bfs有意思的小故事

深搜，顾名思义，是深入其中、直取结果的一种搜索方法。
　　

        如果深搜是一个人，那么他的性格一定倔得像头牛！他从一点出发去旅游，只朝着一个方向走，除非路断了，他绝不改变方向！除非四个方向全都不通或遇到终点，他绝不后退一步！因此，他的姐姐广搜总是嘲笑他，说他是个一根筋、不撞南墙不回头的家伙。
　　深搜很讨厌他姐姐的嘲笑，但又不想跟自己的亲姐姐闹矛盾，于是他决定给姐姐讲述自己旅途中的经历，来改善姐姐对他的看法。他成功了，而且只讲了一次。从那以后他姐姐不仅再没有嘲笑过他，而且连看他的眼神都充满了赞赏。他以为是自己路上的各种英勇征服了姐姐，但他不知道，其实另有原因……
　　深搜是这样跟姐姐讲的：关于旅行呢，我并不把目的地的风光放在第一位，而是更注重于沿路的风景，所以我不会去追求最短路，而是把所有能通向终点的路都走一遍。可是我并不知道往哪走能到达目的地，于是我只能每到一个地方，就向当地的人请教各个方向的道路情况。

        为了避免重复向别人问同一个方向，我就给自己规定：先问北，如果有路，那就往北走，到达下一个地方的时候就在执行此规定，如果往北不通，我就再问西，其次是南、东，要是这四个方向都不通或者抵达了终点，那我回到上一个地方，继续探索其他没去过的方向。

        我还要求自己要记住那些帮过他的人，但是那些给我帮倒忙的、让我白费力气的人，要忘记他们。有了这些规定之后，我就可以大胆的往前走了，既不用担心到不了不目的地，也不用担心重复走以前的路。哈哈哈……

深搜优缺点：

优点：
（1）能找出所有解决方案
（2）优先搜索一棵子树，然后是另一棵，所以和广搜对比，有着内存需要相对较少的优点

缺点：
（1）要多次遍历，搜索所有可能路径，标识做了之后还要取消。
（2）在深度很大的情况下效率不高

广搜，顾名思义，是多管齐下、广撒网的一种搜索方法。

　　如果广搜是一个人，那么她一定很贪心，而且喜新厌旧！她从一点出发去旅游，先把与起点相邻的地方全部游览一遍，然后再把与她刚游览过的景点相邻的景点全都游览一边……一直这样，直至所有的景点都游览一遍。
　　广搜属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。类似树的按层遍历，其过程为：首先访问初始点Vi，并将其标记为已访问过，接着访问Vi的所有未被访问过可到达的邻接点Vi1、Vi2…Vit，并均标记为已访问过，然后再按照Vi1、Vi2…Vit 的次序，访问每一个顶点的所有未被访问过的邻接点，并均标记为已访问过，依此类推，直到图中所有和初始点Vi有路径相通的顶点都被访问过为止。

广搜优缺点：

优点：
（1）对于解决最短或最少问题特别有效，而且寻找深度小
（2）每个结点只访问一遍，结点总是以最短路径被访问，所以第二次路径确定不会比第一次短

缺点
（1）内存耗费量大（需要开大量的数组单元用来存储状态）

注意：以上内容引用自(1条消息) 深搜和广搜的原理及优缺点_June·D的博客-CSDN博客_深搜和广搜

三、深搜题例

其实深搜和广搜的相关定义和性质知道上面的故事也差不多了（doge），主要还是多打打题吧。

1、小猫爬山链接

165. 小猫爬山 - AcWing题库

2、基本思路

见下图：

3、代码

（1）python代码

N,M=map(int,input().split())
ans=N
cat=[0 for _ in range(N+2)]
cap=[0 for _ in range(N+2)]
 
def dfs(now:int,cnt:int)->None:
    global ans,cat,cap
    if cnt>=ans:
        return
    if now==N+1:
        ans=min(ans,cnt)
        return
    
    # 尝试分配到已经租用的缆车上
    for i in range(1,cnt+1):  # 分配到已租用缆车
        if cap[i]+cat[now]<=M:
            cap[i]+=cat[now]
            dfs(now+1,cnt)
            cap[i]-=cat[now] # 还原
    # 新开一辆缆车
    cap[cnt+1]=cat[now]
    dfs(now+1,cnt+1)
    cap[cnt+1]-=cat[now]
 
for i in range(1,N+1):
    cat[i]=int(input())
 
# for i in range(0,N+1):
#     print(cat[i])
 
cat.sort(reverse=True)
cat=[0]+cat
dfs(1,0)
 
print(ans)
 
# for i in range(1,N+1):
#     print(cat[i])

C++代码见acwing题解区。

四、广搜题例

1、武士风度的牛链接

188. 武士风度的牛 - AcWing题库

2、基本思路

据说这一道题很经典，是一道广搜的”模板”题。只需用最原始的广搜，改一下方向即可.

3、代码

（1）C++代码

#include
#include
#include
#include   //广搜需要用到队列是吧，所以我们给它加上一个头文件 
 
#define x first
#define y second
 
using namespace std;
 
typedef pair<int,int> PII;  //很经典的暴搜，首先这个题要搜索两维坐标，所以我们可以用pair存下标，这样的话代码能稍微短一些 
 
const int N=155;
 
int n,m;  // n行m列 
char g[N][N];  // 表示整一张地图 
int dist[N][N]; //表示到每一个格子的最短距离 
 
/*常用技巧  偏移量法  画图可知一个点的日字跳法到周围8个位置的偏移量*/
int dx[]={-2,-1,1,2,2,1,-1,-2};
int dy[]={1,2,2,1,-1,-2,-2, -1}; 
 
int bfs(PII start,PII end){
	queue q;
	memset(dist,-1,sizeof dist);
	dist[start.x][start.y]=0;
	q.push(start);
	
	while(q.size()){
		PII t=q.front();
		q.pop();
		
		for(int i=0;i<8;i++){
			int nx=t.x+dx[i],ny=t.y+dy[i];
			if(nx<0||nx>=n||ny<0||ny>=m||g[nx][ny]=='*'||dist[nx][ny]!=-1)
				continue; 
			dist[nx][ny]=dist[t.x][t.y]+1;
			
			if(make_pair(nx,ny)==end)
				return dist[nx][ny];
			q.push({nx,ny});
		}
	}
	return -1;
}
 
int main(){
	cin>>m>>n;
	for(int i=0;i>g[i];
	
	PII start,end;
	for(int i=0;i
		for(int j=0;j
			if(g[i][j]=='K') start={i,j};
			else if(g[i][j]=='H') end={i,j};
			
	cout<<bfs(start,end)<
	return 0;
} 

（3）python代码

class pair:
    x,y=0,0
    def _init_(self)->None:
        self.x, self.y = 0, 0
 
def bfs(start:pair,end:pair)->int:
    global n,m,dist,g
    dx=[-2,-1,1,2,2,1,-1,-2]
    dy=[1,2,2,1,-1,-2,-2,-1]
    q=[]  # 用列表代替队列快多了
    dist[start.x][start.y]=0
    q.append(start)
 
    while len(q):
        t=q.pop(0)
##        print(t)
        for i in range(8):
            nx,ny=t.x+dx[i],t.y+dy[i]
            if nx<0 or nx>=n or ny<0 or ny>=m or g[nx][ny]=='*' or dist[nx][ny]!=-1:
                continue
            dist[nx][ny]=dist[t.x][t.y]+1
            if nx==end.x and ny==end.y:
                return dist[nx][ny]
            tmp=pair()
            tmp.x,tmp.y=nx,ny
            q.append(tmp)
    return -1
 
N=155
dist=[[-1]*N for _ in range(N)]
g=[]
 
m,n=map(int,input().split())
 
for i in range(n):
    g.append(input())
 
_start=pair()
_end=pair()
 
for i in range(n):
    for j in range(m):
        if g[i][j]=='K':
            _start.x=i
            _start.y=j
        elif g[i][j]=='H':
            _end.x=i
            _end.y=j
 
print(bfs(_start,_end))
 
 
 
'''
from queue import Queue
class pair:
    x,y=0,0
    def _init_(self)->None:
        self.x, self.y = 0, 0
def bfs(start:pair,end:pair)->int:
    global n,m,dist,g
    dx=[-2,-1,1,2,2,1,-1,-2]
    dy=[1,2,2,1,-1,-2,-2,-1]
    q=Queue() #显然这个是可以定义无限长度的
    dist[start.x][start.y]=0
    q.put(start)
    while q.qsize():
        t=q.get()
##        print(t)
        for i in range(8):
            nx,ny=t.x+dx[i],t.y+dy[i]
            if nx<0 or nx>=n or ny<0 or ny>=m or g[nx][ny]=='*' or dist[nx][ny]!=-1:
                continue
            dist[nx][ny]=dist[t.x][t.y]+1
            if nx==end.x and ny==end.y:
                return dist[nx][ny]
            tmp=pair()
            tmp.x,tmp.y=nx,ny
            q.put(tmp)
    return -1
N=155
dist=[[-1]*N for _ in range(N)]
g=[]
m,n=map(int,input().split())
for i in range(n):
    g.append(input())
_start=pair()
_end=pair()
for i in range(n):
    for j in range(m):
        if g[i][j]=='K':
            _start.x=i
            _start.y=j
        elif g[i][j]=='H':
            _end.x=i
            _end.y=j
print(bfs(_start,_end))
'''

以上，dfs和bfs

祝好