BFS | MASON Blog

Brute Force Recursion - BFS

When learning about binary trees, level-order traversal is implemented using BFS.

From binary trees to multi-way trees to graphs, we start from one point and spread out in all directions. Generally, BFS algorithms use a "queue" data structure, where we add all surrounding nodes of a node to the queue.

A common use of BFS is to find the shortest distance from start to target, and we need to be able to transform practical problems into this form.

// In a binary tree, start is the root
function bfs(start, target) {
    const queue = [start]
    const visited = new Set()
    visited.add(start)

    let step = 0
    while (queue.length > 0) {
        const size = queue.length
        /** Spread all nodes in the current queue to their surroundings */
        for (let i = 0; i < size; ++i) {
            const el = queue.shift()
            if (el === target) return step // 'required information'
            const adjs = el.adj() // generally refers to getting all adjacent elements of el
            for (let j = 0; j < adjs.length; ++j) {
                if (!visited.has(adjs[j])) {
                    queue.push(adjs[j])
                    visited.push(adjs[j])
                }
            }
        }
        step++
    }
}

Practice

lc.111 Minimum Depth of Binary Tree easy

/**
 * Can't help but start with a backtracking dfs, but that's not today's main topic 😂 ps: used backtracking here, but could also use the approach of converting to subproblems
 * @param {TreeNode} root
 * @return {number}
 */
var minDepth = function (root) {
    if (root === null) return 0
    let min = Infinity
    const dfs = (root, deep) => {
        if (root == null) return
        if (root.left == null && root.right == null) {
            min = Math.min(min, deep)
            return
        }
        deep++
        dfs(root.left, deep)
        deep--
        deep++
        dfs(root.right, deep)
        deep--
    }
    dfs(root, 1)
    return min
}

/** BFS version */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var minDepth = function (root) {
    // Here we're finding the distance from root to the nearest leaf node (target), once we understand this, the rest is straightforward~
    if (root === null) return 0
    const queue = [root]
    let deep = 0
    while (queue.length) {
        const size = queue.length
        deep++
        for (let i = 0; i < size; ++i) {
            const el = queue.shift()
            if (el.left === null && el.right === null) return deep
            if (el.left) queue.push(el.left)
            if (el.right) queue.push(el.right)
        }
    }
    return deep
}

Have to say, we're quite confident with easy problems 😄.

lc.752 Open the Lock

This is a medium problem, but it's quite challenging and needs careful analysis.

First, it's undoubtedly an exhaustive search problem. Second, a key point in the problem is: each rotation can only turn one digit of one wheel, which allows us to abstract the adjacent nodes. For example, '0000' has neighbors like '1000', '9000', '0100', '0900'... Thus, the problem transforms into finding the shortest path from '0000' to target.

/**
 * @param {string[]} deadends
 * @param {string} target
 * @return {number}
 */
var openLock = function (deadends, target) {
    const queue = ['0000']
    let step = 0
    const visited = new Set()
    visited.add('0000')
    while (queue.length) {
        const size = queue.length
        for (let i = 0; i < size; ++i) {
            const el = queue.shift()
            if (deadends.includes(el)) continue
            if (el === target) return step
            // Add adjacent elements to queue
            for (let j = 0; j < 4; j++) {
                const up = plusOne(el, j)
                const down = minusOne(el, j)
                !visited.has(up) && queue.push(up), visited.add(up)
                !visited.has(down) && queue.push(down), visited.add(down)
            }
        }
        step++
    }
    return -1
}
// First define the +1, -1 operations for each wheel
function plusOne(str, i) {
    const arr = str.split('')
    if (arr[i] == '9') {
        arr[i] = '0'
    } else {
        arr[i]++
    }
    return arr.join('')
}
function minusOne(str, i) {
    const arr = str.split('')
    if (arr[i] == '0') {
        arr[i] = '9'
    } else {
        arr[i]--
    }
    return arr.join('')
}

Let's mention "Bidirectional BFS Optimization": Traditional BFS framework spreads from the starting point until it reaches the target, while bidirectional BFS spreads from both the start and target points simultaneously, stopping when there's an intersection between the two sides. labuladong

lc.773 Sliding Puzzle hard

Another classic game from childhood. Beginners really can't figure out how to solve it, and even those who know the method struggle with transforming the practical problem into a BFS problem.

Let's analyze it step by step: 1. Each time, the empty position 0 makes a choice, moving adjacent elements up, down, left, or right to the 0 position. 2. The target is [[1,2,3],[4,5]], how do we handle this? Following the previous problem's approach, if we convert it to a string, wouldn't it be much easier? The difficulty lies in how to compress the 2D array into a 1D string while recording the neighbor indices of each number.

A technique is: For an m x n 2D array, if an element e in the 2D array has index i in the 1D array, then e's left and right adjacent elements in the 1D array have indices i - 1 and i + 1, while e's up and down adjacent elements have indices i - n and i + n, where n is the number of columns in the 2D array.

Of course, for this 2*3 problem, we can write it directly 😁.

/**
 * @param {number[][]} board
 * @return {number}
 */
const neighbors = [
    [1, 3],
    [0, 2, 4],
    [1, 5],
    [0, 4],
    [1, 3, 5],
    [2, 4]
]
// Kind of like an adjacency list~
var slidingPuzzle = function (board) {
    let str = ''
    for (let i = 0; i < board.length; ++i) {
        for (let j = 0; j < board[0].length; ++j) {
            str += board[i][j]
        }
    }
    const target = '123450'
    const queue = [str]
    const visited = [str] // could use Set too~
    let step = 0
    while (queue.length) {
        const size = queue.length
        for (let i = 0; i < size; ++i) {
            const el = queue.shift()
            if (el === target) return step

            /** Find the index of 0 and swap with its surrounding elements */
            const idx = el.indexOf('0')
            for (const neighborIdx of neighbors[idx]) {
                // Need to convert to array for swapping
                const newEl = swap(el, idx, neighborIdx)
                if (visited.indexOf(newEl) === -1) {
                    // Don't go back
                    queue.push(newEl)
                    visited.push(newEl)
                }
            }
        }
        step++
    }
    return -1
}
function swap(str, i, j) {
    const chars = str.split('')
    const temp = chars[i]
    chars[i] = chars[j]
    chars[j] = temp
    return chars.join('')
}