广度优先搜索算法（Breadth-First-Search）

算法专栏

September 1, 2020 小羽

7 minute read

上次在介绍完功能强大的深度优先搜索算法(DFS)后，这次我来给大家介绍一下另一个功能类似且同样强大的经典算法——广度优先搜索算法 Breadth-First-Search（BFS）。

I. 算法定义

BFS同DFS一样，是一种用于遍历、搜索树或图的一种搜索算法。与DFS会先一路走到黑不同，BFS会从根节点开始搜索，在每一个路口面临分叉的时候，先把每个岔路记录下来，然后再去一个一个的往前走一步。

左下图是BFS搜索路线的一个例子。加入我们要找的是节点5。BFS首先搜索根节点0，然后会依次搜索它的两个子节点(节点1,节点2)，路线为：0->1->2。接着会去搜索节点1和节点2的子节点（节点3，4，5，6），所以最终路线为：0->1->2->3->4->5。

BFS的时间复杂度为O(N + M)，N为节点的数量，M为边的数量。

avatar

II. 实现方法

由于BFS会在每个岔路口首先储存所有岔道的特性，通常BFS会和Queue（先进先出）一同使用。步骤如下：

将根节点加入到Queue中
使用while循环，当Queue为空时，结束循环。
将Queue中的节点依次poll出来检查。
如果没有找到要找的值，就将poll出来的节点的子节点再加入到Queue中（如果没有子节点就不加）。

III. 使用场景

常见的数据结构

BFS通常在图(graph)或者二叉树(BST)(实际上BST是一种特殊的图)上使用。在图上使用时，我们往往使用HashSet或者HashMap来避免指针向回走。

常见的使用场景

1.连通块问题（Connected Component）

连通块问题是指通过一个点找到图中所联通的所有点的问题。这类问题我们可以用经典的BFS加上HashSet来解决。

2.分层遍历（Level Order Traversal）

分层遍历问题要求我们在图中按层次进行遍历，常见的分层遍历问题有简单图的最短路径问题(Simple Graph Shortest Path)

Note: 简单图指的是每条边的距离相等，或者都视作长度为单位1的图。

3.拓扑排序（Topological Sorting）

拓扑排序是一种对图中节点的排序。在这种排序中，假若A点指向B点，则A点的序在B点前。同一种图可能有不同的拓扑序。BFS可以用来求任意拓扑序、求一张图是否有拓扑序（如果是图中存在循环则没有拓扑序）、求字典序最小的拓扑序和求图中是否有唯一拓扑序。

在拓扑排序中，我们首先要计算出每个点的入度(In-degree)。入度指的是一共有多少条边指向这个点。用BFS解决拓扑排序问题的算法步骤如下：

a). 统计每个点的入度

b). 将入度为0的所有点放入Queue中作为起始节点

c). 依次从Queue中取出一个节点，并将它指向的点的入度-1。

d). 如果它指向的点的入度为0了，就将其添加进Queue中。

IV. 经典习题

1.连通块问题（Connected Component）

a. Number of Islands(Lintcode 433)

Description

English

Given a boolean 2D matrix, 0 is represented as the sea, 1 is represented as the island. If two 1 is adjacent, we consider them in the same island. We only consider up/down/left/right adjacent.

Find the number of islands.

Chinese

给一个 01 矩阵，求不同的岛屿的个数。

0 代表海，1 代表岛，如果两个 1 相邻，那么这两个 1 属于同一个岛。我们只考虑上下左右为相邻。

图片名称

这道题是一道典型的连通块问题。我们可以用两个for循环遍历整个矩阵，如果遇到岛屿就用bfs对其进行标记并且统计岛屿的数量。

Note: 在矩阵的计算中，我们常常使用is_valid()函数来检测是否越界

Python代码

DIRECTIONS = [(1, 0), (0, -1), (-1, 0), (0, 1)]

class Solution:
    
    """
    @param grid: a boolean 2D matrix
    @return: an integer
    """
    def numIslands(self, grid):
        # write your code here
        if not grid or not grid[0]:
            return 0
            
        visited = set()
        result = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] and (i, j) not in visited:
                    self.bfs(grid, i, j, visited)
                    result += 1
                    
        return result
        
    def bfs(self, grid, x, y, visited):
        queue = collections.deque([(x, y)])
        visited.add((x, y))
        while queue:
            x, y = queue.popleft()
            for dx, dy in DIRECTIONS:
                new_x = x + dx
                new_y = y + dy
                if not self.is_valid(grid, new_x, new_y, visited):
                    continue
                queue.append((new_x, new_y))
                visited.add((new_x, new_y))
    
    def is_valid(self, grid, x, y, visited):
        n, m = len(grid), len(grid[0])
        if not (0 <= x < n and 0 <= y < m):
            return False
        if (x, y) in visited:
            return False
        return grid[x][y]

代码解析

a. 定义常量DIRECTIONS，其定义了每个点可以向上下左右四个方向移动：

DIRECTIONS = [(1, 0), (0, -1), (-1, 0), (0, 1)]

b. 异常检测：

if not grid or not grid[0]:
  return 0

c. 申明visitedset用来出存已经访问过的点，申明result变量用来储存岛屿的数量：

visited = set()
result = 0

d. for循环遍历整个矩阵，如果遍历到一个没有访问过的岛屿就对其进行bfs且将result+1：

for i in range(len(grid)):
  for j in range(len(grid[0])):
    if grid[i][j] and (i, j) not in visited:
      self.bfs(grid, i, j, visited)
      result += 1

e. bfs函数找到这个岛屿所有的点并标记：

def bfs(self, grid, x, y, visited):
  queue = collections.deque([(x, y)])	#申明一个Queue
  visited.add((x, y))	#标记
  while queue:
    x, y = queue.popleft()	#取出第一个节点
    for dx, dy in DIRECTIONS:	#计算出这个节点向不同方向移动后的新节点
      new_x = x + dx
      new_y = y + dy
      if not self.is_valid(grid, new_x, new_y, visited):	#如果节点合法就将其标记且加入到Queue中
        continue
        queue.append((new_x, new_y))
        visited.add((new_x, new_y))

e. is_valid函数用来判断点是否合法：

def is_valid(self, grid, x, y, visited):
  n, m = len(grid), len(grid[0])	
  if not (0 <= x < n and 0 <= y < m):	#判断是否越界
    return False
  if (x, y) in visited:	#判断是否被访问过
    return False
  return grid[x][y]

2.分层遍历（Level Order Traversal）

Knight Shortest Path(Lintcode 611)

Description

English

Given a knight in a chessboard (a binary matrix with 0 as empty and 1 as barrier) with a source position, find the shortest path to a destination position, return the length of the route. Return -1 if destination cannot be reached.

source and destination must be empty. Knight can not enter the barrier. Path length refers to the number of steps the knight takes.

Chinese

给定骑士在棋盘上的 初始 位置(一个2进制矩阵 0 表示空 1 表示有障碍物)，找到到达 终点 的最短路线，返回路线的长度。如果骑士不能到达则返回 -1 。

起点跟终点必定为空. 骑士不能碰到障碍物. 路径长度指骑士走的步数.

图片名称

这道题是一道典型的求最短路径的题。在求解这类问题的时候，我们只需要把求解连通块问题的BFS算法中的Hashset改为Hashmap即可。Hashmap用来标记访问过的点且记录到达每个点的最短路径。

在这道题目中，我们需要首先定义棋子的走法，然后用一个BFS分层遍历直到找到终点为止（或者所有点都越界），最后返回终点在Hashmap中所对应的步数即可。

Python代码

"""
Definition for a point.
class Point:
    def __init__(self, a=0, b=0):
        self.x = a
        self.y = b
"""
DIRECTIONS = [
    (-2, -1), (-2, 1), (-1, 2), (1, 2),
    (2, 1), (2, -1), (1, -2), (-1, -2)
]
class Solution:
    """
    @param grid: a chessboard included 0 (false) and 1 (true)
    @param source: a point
    @param destination: a point
    @return: the shortest path 
    """
    def shortestPath(self, grid, source, destination):
        # write your code here
        if not grid:
            return -1
        

        queue = collections.deque([(source.x, source.y)])
        distance = {(source.x, source.y): 0}
        while queue:
            x, y = queue.popleft()
            if x == destination.x and y == destination.y:
                return distance[(x, y)]
            for dx, dy in DIRECTIONS:
                next_x, next_y = x + dx, y + dy
                if self.is_valid(next_x, next_y, grid):
                    if (next_x, next_y) not in distance:
                        distance[(next_x, next_y)] = distance[(x, y)] + 1
                        queue.append((next_x, next_y))

        return -1
    
    def is_valid(self, x, y, grid):
        m, n = len(grid), len(grid[0])
        if 0 <= x < m and 0 <= y < n and grid[x][y] == 0:
            return True
        else:
            return False

代码解析

a. 定义走法：

DIRECTIONS = [(-2, -1), (-2, 1), (-1, 2), (1, 2), (2, 1), (2, -1), (1, -2), (-1, -2)]

b. 异常检测：

if not grid:
  return -1

c. 定义一个Queue，将起点放进去；定义一个Hashmap distance，其key为坐标，其value为最短路径。将起点放入Hashmap：

queue = collections.deque([(source.x, source.y)])
distance = {(source.x, source.y): 0}

d. 开始bfs，每次循环从queue中取出一个点，如果这个点和终点相等就返回它在Hashmap中的最短路径。如果不等，找到下一步所有的走法，如果他们合法且不在Hashmap中，那么将他们加入到Hashmap中，且加入到Queue中：

while queue:	#如果queue不为空，循环继续
  x, y = queue.popleft()	#取出第一个点
  if x == destination.x and y == destination.y:	#如果此点等于终点，返回它在Hashmap中记录的最短路径
    return distance[(x, y)]
  for dx, dy in DIRECTIONS:	#遍历所有可以走的新点
    next_x, next_y = x + dx, y + dy
    if self.is_valid(next_x, next_y, grid):	
      if (next_x, next_y) not in distance:	#如果这个点合法且不在Hashmap中
        distance[(next_x, next_y)] = distance[(x, y)] + 1	#将新的点加入Hashmap
        queue.append((next_x, next_y))	#将新的点加入queue中

e. is_valid函数用来判断点是否越界：

def is_valid(self, x, y, grid):
  m, n = len(grid), len(grid[0])
  if 0 <= x < m and 0 <= y < n and grid[x][y] == 0:
    return True
  else:
    return False

3.拓扑排序（Topological Sorting）

Description

English

Given an directed graph, a topological order of the graph nodes is defined as follow:

For each directed edge A -> B in graph, A must before B in the order list.
The first node in the order can be any node in the graph with no nodes direct to it.

Find any topological order for the given graph.

You can assume that there is at least one topological order in the graph.

Chinese

给定一个有向图，图节点的拓扑排序定义如下:

对于图中的每一条有向边 A -> B , 在拓扑排序中A一定在B之前.
拓扑排序中的第一个节点可以是图中的任何一个没有其他节点指向它的节点.

针对给定的有向图找到任意一种拓扑排序的顺序.

你可以假设图中至少存在一种拓扑排序

图片名称

这道题要我们返回图的任意拓扑序。解题思路是这样的：

a. 计算出每个点的入度并记录在Hashmap中

b. 申明一个Queue，将入度为0的点放进去

c. 用BFS遍历Queue，将Queue中取出来的所有点加入结果数组，其所有neighbor的入度-1

d. 如果neighbor点的入度为0了，将其加入Queue中。

Python代码

"""
Definition for a Directed graph node
class DirectedGraphNode:
    def __init__(self, x):
        self.label = x
        self.neighbors = []
"""


class Solution:
    """
    @param: graph: A list of Directed graph node
    @return: Any topological order for the given graph.
    """
    def topSort(self, graph):
        # write your code here
        if not graph:
            return []
            
        #add in-degree
        node_to_indegree = self.get_indegree(graph)
        
        #bfs
        order = []
        start_node = [n for n in graph if node_to_indegree[n] == 0]
        queue = collections.deque(start_node)
        while queue:
            node = queue.popleft()
            order.append(node)
            for neighbor in node.neighbors:
                node_to_indegree[neighbor] -= 1
                if node_to_indegree[neighbor] == 0:
                    queue.append(neighbor)
                    
        return order
                
    def get_indegree(self, graph):
        node_to_indegree = {x: 0 for x in graph}

        for node in graph:
            for neighbor in node.neighbors:
                node_to_indegree[neighbor] += 1
                
        return node_to_indegree

代码解析

a. 异常检测：

if not graph:
  return []

b. 计算出所有点的入度：

node_to_indegree = self.get_indegree(graph)

def get_indegree(self, graph):
  node_to_indegree = {x: 0 for x in graph}	#初始化所有点的入度为0

  for node in graph:	#遍历图中的每个点的所有neighbor,将其neighbor的入度+1
    for neighbor in node.neighbors:	
      node_to_indegree[neighbor] += 1

      return node_to_indegree

c. 定义结果数组和Queue，并将入度为0的点加入其中：

order = []
start_node = [n for n in graph if node_to_indegree[n] == 0]
queue = collections.deque(start_node)

d. 开始bfs算法，将queue中取出的点加入结果数组中，并将其所有neighbor的入度-1，如果neighbor点的入度为0了，将其加入Queue：

while queue:	#当queue非空时，继续循环
  node = queue.popleft()	#取出第一个点
  order.append(node)	#将点加入结果数组中
  for neighbor in node.neighbors:	#遍历点的所有neighbor
    node_to_indegree[neighbor] -= 1	#将neighor的入度-1
    if node_to_indegree[neighbor] == 0:	#如果入度为0，将其加入queue
      queue.append(neighbor)

4.附加题目

a. Minimum Depth of Binary Tree(Leetcode 111)

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Note: A leaf is a node with no children.

avatar

这道题非常简单，找到一个最浅的节点，其没有子节点并返回它的深度。

需要的变量:

Queue<TreeNode> queue = new LinkedList<>();
int depth = 0;

Queue queue, int depth。

步骤

我们首先将根节点加入到queue中，将depth初始化为0。
开始while循环，当queue为空时停止循环。每一次循环就是BFS中把每一个岔路都遍历的过程。
每次循环depth++。
将queue中的所有值用for循环依次poll出来，如果其没有子节点，就返回depth；如果只有一个子节点为null，那么就将另一个offer进queue里。如果两个子节点都不为null，将它们依次offer到queue中。

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int minDepth(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        int depth = 0;
        if (root == null) return depth;
        queue.add(root);
        while (!queue.isEmpty()){
            depth++;
            int size = queue.size();
            for (int i=0; i<size; i++) {
                TreeNode q = queue.poll();
                if (q.left == null && q.right == null) return depth;
                if (q.left != null) queue.offer(q.left);
                if(q.right != null) queue.offer(q.right);
            }
        }
        return depth;
    }
}

b. Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

avatar

这道题要求我们写一个函数：输入一个Binary Tree，返回一个List>,其中包含每一层的所有值。

需要的变量

List<List<Integer>> result = new LinkedList<>();	//储存结果
Queue<TreeNode> queue = new LinkedList<>();				//用于进行BFS

思路

将根节点加入到queue中。
开始while循环，当queue为空时停止。每一次循环就是BFS中把每一个岔路都遍历的过程。
创建一个list用于储存每一层节点的值，当一层变量结束时，将其add到result中。
用for循环依次poll出queue中的所有节点，把节点的值加入到list中。
如果poll出来的节点的子节点不为空就将其offer到queue中。
如果list不为空，就将其add到result里面去。
返回result

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {

   public  List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new LinkedList<>();
        if (root == null) return result;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> list = new ArrayList<>();
            int size = queue.size();
            for (int i=0; i<size; i++) {
                TreeNode q = queue.poll();
                list.add(q.val);
                if (q.left != null) queue.offer(q.left);
                if (q.right != null)   queue.offer(q.right);
                }
            if (!list.isEmpty()) result.add(new ArrayList<>(list));
        }
        return result;
   }
}

V. 总结

BFS是一种在图、搜索树和遍历中非常经典且常用的算法。其思路为先找到节点的每一个岔路并标记起来，再依次往前更进一步，直到找到结果或遍历完为止。做法通常为将起始点加入到queue中，然后将queue中的节点取出，搜索结果。如果结果不在，就将节点的子节点继续放到queue中重复以上过程直到找到结果或遍历完所有节点为止。

VI. 参考

https://www.jiuzhang.com/

https://leetcode.com/

https://www.lintcode.com/

blog

首页

关于

博客

归档

分类

标签

联系

近期博文

Git简明教程

SpringBoot总结

Docker 总结

SpringMVC总结

Spring总结

广度优先搜索算法（Breadth-First-Search）

I. 算法定义

II. 实现方法

III. 使用场景

IV. 经典习题

V. 总结

VI. 参考

YY的主页

近期博文

Git简明教程

SpringBoot总结

Docker 总结

SpringMVC总结

Spring总结

分类

关于