算法系列之广度优先搜索

广度优先搜索

    广度优先搜索（BFS）是连通图的一种遍历策略。因为它的思想是从一个顶点V0开始，辐射状地优先遍历其周围较广的区域，故得名。

    广度优先搜索，又可以叫层次遍历

    广度优先搜索需要一个队列，把根节点加入队列中，然后弹出根节点，将根节点的子节点依次加入到队列中，不断循环，直到队列为空，这样我们就辐射状的遍历了整个树（图）。

1、基本流程

1）BFS遍历过程

    以最短路径问题为例，找到下图中V0—V6的最短路径

    我们从V0出发，此时V0在队列中，给V0标记状态（灰色）

    将V0弹出，改变V0的状态（黑色，表示已经遍历过），将其子节点V1、V2、V3加入队列中，改变其标记状态

    依次将V3、V2、V1（队列先进后出）弹出，改变其状态，并将各自的子节点依次加入队列中

    这样循环，直到遍历到V6，此时返回遍历到V6的路径

2）BFS算法流程图

2、算法比较与应用 BFS VS DFS

• BFS是用来搜索最短径路的解是比较合适的，比如求最少步数的解，最少交换次数的解，因为BFS搜索过程中遇到的解一定是离根最近的，所以遇到一个解，一定就是最优解，此时搜索算法可以终止。而DFS搜索到的解不一定是离根最近的，只有全局搜索完毕，才能从所有解中找出离根的最近的解。
• 空间代价上，DFS是有优势的，DFS不需要保存搜索过程中的状态，而BFS在搜索过程中需要保存搜索过的状态，而且一般情况需要一个队列来记录。
• DFS适合搜索全部的解，因为要搜索全部的解，那么BFS搜索过程中，遇到离根最近的解，并没有什么用，也必须遍历完整棵搜索树，DFS搜索也会搜索全部，但是相比DFS不用记录过多信息，所以搜素全部解的问题，DFS显然更加合适。

3、经典题目

1）迷宫类问题

问题

1. 一个矩阵， 里面0表示空的地方，1表示是石头， 然后有一个开始的位置和结束的位置
2. 从任何一个位置，都有上下左右4个方向， 然后每次都要走到1或者边界才停止
3. 问从左上角走到右下角的最短路径是多少

举例

    对于下面的迷宫，找到其从maze[0][0]到maze[4][4]的最短路径距离

maze = [[0,1,0,0,0],
		[0,1,0,1,0],
		[0,0,0,0,0],
		[0,1,1,1,0],
		[0,0,0,1,0]]

思路

    迷宫类问题跟上面所说的图的遍历是一样的，在这里每个0点就是一个节点，两个0挨着，说明其之间有边，其起点为maze[0][0]点，终点为maze[4][4]点

def BFS(maze:List[List[int]])->int:
    #maze为迷宫地图，start为开始节点[0,0]，end为结束节点[M-1,N-1]
    Quene = []			#定义一个队列
    M = len(maze)		#行数
    N = len(maze[0])	#列数
    visit = [[False]*N for _ in range(M)]	#标记黑色状态
    dir = [[0,1],[1,0],[0,-1],[-1,0]]		#分别表示右、下、左、上四个方向
    start = [0,0,0]     #最后一个0表示步数
    end = [M-1,N-1]

    #队列中首先加入开始点
    Quene.append(start)	
    visit[start[0]][start[1]] = True
    while(len(Quene)!=0):
        x,y,step = Quene.pop(0)
        for dx,dy in dir:
            Vw = [x+dx,y+dy,step+1]
            if([x+dx,y+dy] == end):		#如果找到了终点
                return step+1
        	#如果移动有效，且该节点未遍历过，则添加到队列中
            if(isValid(maze,Vw) and not visit[Vw[0]][Vw[1]]):
                Quene.append(Vw)
                visit[Vw[0]][Vw[1]] = True
        	
    return -1

def isValid(maze:List[List[int]],V:List[int])->bool:
    #判断该节点是否在地图的有效位置上
    M = len(maze)		#行数
    N = len(maze[0])	#列数
    if (V[0] >=0) and (V[0] <= M-1) and (V[1] >=0) and (V[1] <= N-1) and maze[V[0]][V[1]] == 0:
        return True
    return False

参考链接

• 广度/宽度优先搜索(BFS)
• 九章算法某回答