preface
BFS and DFS are two search methods that go hand in hand. We learned the concept of recursion and DFS from the three Leetcode masters of Depth-first Search (DFS) in the last article. For those unfamiliar with recursion and DFS, it’s a good idea to read this article first.
BFS
The difference between BFS and DFS is that
-
DFS is a way to go black, searching the deepest layer and then returning to the top layer.
-
BFS is a step by step process, where all data is searched and then the next level is searched.
As an example, let’s take a look at the traversal order using BFS
-
Single node A is searched from the first layer
-
The second layer search results in path B -> C -> D
-
The third layer search results in path E -> F -> G -> H
-
Similarly, to continue the lower level search, the best complete path is A -> B -> C -> D -> E -> F -> G -> H -> I -> J -> K
1. Sequence traversal of binary tree
Let’s do a simple binary tree traversal
leetcode-102
Give you the root node of the binary tree, root, and return the sequential traversal of its node value. (That is, layer by layer, all nodes are accessed from left to right).
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */
/ * * *@param {TreeNode} root
* @return {number[][]}* /
var levelOrder = function(root) {
if(! root)return []
// First define the answer traversal
const ans = []
// Our BFS function
// We can find that BFS and DFS have different variables
// the BFS parameter is an array because we are searching the entire layer
const BFS = (nodes) = > {
/ / BFS exports
if(! nodes.length)return
// We need to save the data of the next layer through the extra array to pass to the next layer search
const next = []
const layser = []
// Search iteratively for the current layer
for (let i = 0, len = nodes.length; i < len; i++) {
const node = nodes[i]
layser.push(node.val)
// The point of BFS is that it does not recurse child node data directly
// The underlying data is stored in an array
// Only this layer of data is processed in this layer to achieve clear hierarchy
if(node.left) {
next.push(node.left)
}
if (node.right) {
next.push(node.right)
}
}
ans.push(layser)
// Recurse the underlying data
BFS(next)
}
// An array of arguments
BFS([root])
return ans
};
Copy the code2. Maximum area of the island
We solved this problem through DFS in the last article, and now we are solving this problem through BFS, you can compare the two methods of implementation difference.
leetcode-695
Give you a binary matrix grid of size M x N.
An island is a combination of adjacent 1’s (land) that must be adjacent in all four directions, horizontal or vertical. You can assume that all four edges of the grid are surrounded by zeros (for water).
The area of an island is the number of cells on the island with a value of 1.
Calculate and return the largest island area in the grid. If there are no islands, the return area is 0.
var maxAreaOfIsland = function(grid) {
// m/n is used to compare boundaries
const m = grid.length
const n = grid[0].length
// Define the output variable
let ans = 0
/ / BFS function
// The parameters are also arrays
const BFS = (grids) = > {
/ / BFS exports
if(! grids.length)return 0
const nextGrids = []
let count = 0
// Process the current layer
for (let i = 0, len = grids.length; i < len; i++) {
const [row, col] = grids[i]
/ / the pruning
if (grid[row][col] === 1) {
// Add data to the current layer
count++
grid[row][col] = 0
// Store lower-level data for use by lower-level functions
if (row > 0) {
nextGrids.push([row - 1, col])
}
if (row + 1 < m) {
nextGrids.push([row + 1, col])
}
if (col > 0) {
nextGrids.push([row, col - 1])}if (col + 1 < n) {
nextGrids.push([row, col + 1])}}}// Returns the cumulative value
return count + BFS(nextGrids)
}
// A two-dimensional array has no root node
// So you have to traverse each cell to do a BFS search up, down, left, and right
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === 1) {
// Compare and update the answers
ans = Math.max(BFS([[i, j]]), ans)
}
}
}
return ans
};
Copy the code3. 01 matrix
Let’s take a look at another problem that was specifically designed for BFS
leetcode-542
Given a matrix mat consisting of 0 and 1, output a matrix of the same size, where each cell is the distance from the element at the corresponding position in MAT to the nearest 0.
The distance between two adjacent elements is 1.
BFS and DFS can be used to search the distance between a node and the nearest 0. If using DFS to search, we need a recursive search until search to 0, but the distance is not a simple child nodes (up and down or so) + 1, but have to go through horizontal comparison to get the minimum + 1, and in order to avoid duplication, we need to do to deal with the heavy again, so the algorithm can become very complex.
BFS is very suitable for solving this kind of problem, which is called multi-source shortest path.
We wanted to solve for the distance from 1 to 0, and we thought backwards, updating the distance around 1 by 0. By updating the distance of 1 around 0 synchronously, such as updating the distance of 1 adjacent to 0 first, and updating the distance of 1 adjacent to 1 in the second step, the shortest distance can be determined through layer upon layer of overflow search, and can be determined directly, without comparison and update, we just need to avoid repeated updates.
var updateMatrix = function(mat) {
const ans = []
M/n / / boundary
const m = mat.length
const n = mat[0].length
// Multi-source shortest path source
const queue = []
// up, down, left, right
const dirs = [
[1.0], [...1.0],
[0.1],
[0, -1]]/ / BFS function
const BFS = (grids) = > {
/ / BFS exports
if(! grids.length)return
// Next level of data
const next = []
// This layer of data search
for (let i = 0, gridsLen = grids.length; i < gridsLen; i++) {
const [row, col] = grids[i]
// Look up, down, left, and right
for (let i = 0, len = dirs.length; i < len; i++) {
const dir = dirs[i]
const x = row + dir[0]
const y = col + dir[1]
if (x >= 0 && y >= 0 && x < m && y < n && ans[x][y] === undefined) {
ans[x][y] = ans[row][col] + 1
next.push([x, y])
}
}
}
// Process the underlying data recursively
BFS(next)
}
for (let i = 0; i < m; i++) {
ans[i] = []
for (let j = 0; j < n; j++) {
if (mat[i][j] === 0) {
queue.push([i, j])
// We just add source (0) to ans
// Undefined
// We can get over it
ans[i][j] = 0
}
}
}
BFS(queue)
return ans
};
Copy the codeA non-recursive implementation of BFS
All of our BFS functions are implemented by recursively calling themselves. After processing the data in this layer, we call themselves to process the data in the lower layer until we encounter an exit. In contrast to DFS, recursive calls are very explicit and always start from N -> N +1, so we can do this via queues as well.
Its general realization principle is as follows:
We set the global queue, and then we add layer 1 data to the queue
const quque = []
queue.push(1)
Copy the codeIt then iterates through the queue, adding the underlying data to the queue
queue.push(2) / / [1, 2]
queue.push(2) / / [1, 2, 2)
Copy the codeYou can see that the data at the next level is always behind the current level, thus achieving hierarchical traversal.
Let’s take the third question above
var updateMatrix = function(mat) {
const ans = []
const m = mat.length
const n = mat[0].length
const queue = []
const dirs = [
[1.0], [...1.0],
[0.1],
[0, -1]]for (let i = 0; i < m; i++) {
ans[i] = []
for (let j = 0; j < n; j++) {
if (mat[i][j] === 0) {
queue.push([i, j])
ans[i][j] = 0}}}// We use global queues to store search nodes
// Implement BFS by continuously progressing search
while(queue.length) {
// Pop up the first data through the queue operation
const grid = queue.shift()
const [row, col] = grid
for (let i = 0, len = dirs.length; i < len; i++) {
const dir = dirs[i]
const x = row + dir[0]
const y = col + dir[1]
if (x >= 0 && y >= 0 && x < m && y < n && ans[x][y] === undefined) {
ans[x][y] = ans[row][col] + 1
// The underlying data is queued
queue.push([x, y])
}
}
}
return ans
};
Copy the codeWe can carefully compare the differences between the two implementations, and we can use either one in the future, depending on personal preference.
BFS template
With the above exercise, we summarize the BFS template
- Recursive model
const BFS = (list) = > {
/ / export
if(! list.length)return
// The underlying data array
const next = []
for (let i = 0; i < list.length; i++) {
// Process the current node
// Collect the underlying data
next.push(node.child)
}
// Call the underlying data recursively
BFS(next)
}
Copy the code- Queue mode
const fn = () = > {
// Set the global queue
const quque = []
// Add layer 1 nodes
queue.push(...)
// Iterate over the data
while(queue.length) {
// Keep popping the first node to empty the queue and get the exit
const node = quque.shift()
// Process the current node
// Add the underlying node
queue.push(node.child)
}
}
Copy the codeconclusion
Let’s sum up the knowledge points of this article
-
BFS and DFS are two common search methods, one is depth-first and don’t look back, the other is breadth-first and layer by layer
-
BFS can be implemented in two ways, queue and recursive
-
BFS also requires setting up function exits to prevent infinite loops or recursion
-
BFS is more suitable for multi-source shortest path problems than DFS
-
Common templates for BFS