Breadth-First Search in a 2D Matrix
Tags: javascript, bfs, graphtraversal, nearestexit
Published: 2024-02-24 18:07:14

**O**ne of the most tricky algorithms I've come across so far has been those involving bread-fir....er, I mean breadTH-first searches (**BFS**) in a 2D matrix. Often times you can recognize these algorithms based on the prompt for the challenge. If the description is saying something along the lines of "find the shortest path" and a 2D matrix is involved, chances are that's a big hint to use a BFS. 

Before we dive into the intuition, implementation and finally the solution, I first want to point out that this type of BFS is much different from that of a binary search tree BFS. Though some similarities exist, the data structures are different (binary search tree BFS are tree-based and this BFS is graph-based).

And with that, let's first explore the intuition behind a BFS!

---

![BFS Intuition 1/2](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/4do3m7er7nusc24rf7td.JPG)

---

This representation of a typical BFS was created by [Reducible](https://www.youtube.com/@Reducible) on YouTube and I _highly_ recommend checking them out and giving them a sub. Reducible's [video](https://www.youtube.com/watch?v=xlVX7dXLS64) covers this concept very well, but the gist of  it is depicted succinctly here; the green lines illuminating the path on the vertices (points) shows the order of the initial traversal: 

---

> ## 0 -> 1
## 0 -> 2
## 1 -> 3
## 1 -> 4
## 3 -> 5
## 5 -> 6
## 5 -> 7

---

The reasoning for that order of searching can be found within the algorithm's name: _BREADTH_-first. Basically that means for each vertex, the search is going to visit its closest neighbors first, and when that initial vertex doesn't have any unvisited neighbors left, the search will continue on with one of the closest neighbors to the previous vertex. That pattern continues on until we reach the ending point (in this case, **7**).

---

![BFS Intuition 2/2](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/1dla4wilmq60yqzttxub.JPG)

---

Once we've visited all vertices, the BFS will be able to tell the shortest path to the ending point, as denoted by the yellow line that's illuminating the path. In fact, once we've reached the end-point from the initial search, the BFS will be able to automatically know what that shortest path is! 

That path for this example is: 

---

> ## 0 -> 1 -> 3 -> 5 -> 7

---

A total of **4** steps to go from the starting to the end-point. It's also important to note that the order in which the BFS makes its traversal does _not_ matter. So in the previous initial traversal, **0** could have gone to **2** first, instead of **1**, and that would still be a valid BFS.

Now that we have a general idea of how a BFS operates, let's explore some of the implementations of doing so.

---

The bare-bones, most basic components of a BFS are as follows:

---

**1.** Initialize a new array that will keep track of **_visited_** vertices. All vertices will be unvisited upon the initial pass.



**2.** Nearly all BFS make use of a _queue_ in some shape or form. Remember that queues operate on a "first-in, first-out" basis. This queue will be used to keep track of all the **_unvisited_** vertices, to indicate that we still need to visit them. At the end of the day though, this queue is just another array.



**3.** A while loop is generally used as the "engine" to keep the BFS train rolling. This while loop will keep going as long as the queue in step 2 still has _unvisited_ vertices in it. If there _are_ unvisited vertices in the queue, we'll need to remove the first vertex in the queue and mark it as being visited, which is done by populating our _visited_ array that was mentioned in step 1.



**4.** Once we've marked a vertex as visited, we'll need to implement another iterative method (usually a `for` loop) to iterate over _all_ of the neighbors for the vertex we just marked as visited. During the iteration, we'll add those neighbors into the queue as being unmarked.

---

To reinforce all of that _terribly_ confusing theory, watch this section on Reducible's [video](https://youtu.be/xlVX7dXLS64?si=Sq8V6k9ek-RwIgRu&t=159) about BFS. While the code for it is pretty high-level, they do a great job showing how all of this plays out.

Another resource I **greatly** recommend checking out is this site called [Visualgo](https://visualgo.net/en/sssp?slide=6). That link goes to the BFS subsection of a larger instruction on graph-traversal methods. Click on the green highlighted text that says `BFS(5)`. On the bottom right, you can see the actual code implementation (which is in Java 🤮 but you can get a good idea of what's happening). You can also pause the auto-play feature and click step by step on what's happening (it goes way too fast for me, personally).

---

## SO
with all of this theory and not enough JavaScript code, you're probably wondering if you just wasted all this time, only to come away empty-handed, huh? Well fear not, I came across a pretty incredible solution to solving this algorithm **AND** it isn't a wall of code like you've probably seen before on solving these types of problems! I mean, just look at this:

---


![incredibly long snippet of code](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/38zjtr4q948uxpwq5xa3.JPG)

---


![eyes burning](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/lgybj80jaac4i59djyii.gif)

**W**hile I do greatly appreciate the theory behind such approaches, it just doesn't seem intuitive to me to try and grasp all at once. 

To illustrate a BFS with a concrete example, I'll be using LeetCode's [Nearest Exit from Entrance in Maze](https://leetcode.com/problems/nearest-exit-from-entrance-in-maze/description/) challenge. This solution was **NOT** my own work, just to clarify. This incredibly elegant solution was done by [Maxim](https://www.linkedin.com/in/maximzorin/) and it is a thing of beauty. And without further ado, here is the solution: 

---

![solution to leetcode's nearest exit challenge](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/6hwgomfqeg3kmv6ci33m.JPG)

---

And here's a copypasta if you wish to play around with it:

---

```
*/
/** 
 * @param {string[][]} maze
 * @param {number[]} entrance
 * @return {number}
 */
const nearestExit = (maze, [y0, x0]) => {
    console.log([y0, x0])
    maze[y0][x0] = '@';
    const queue = [[y0, x0, 0]];

    while (queue.length) {
        const [y, x, step] = queue.shift();

        for (const [dy, dx] of [[-1, 0], [0, -1], [1, 0], [0, 1]]) {
            const ny = y + dy, nx = x + dx;

            if (!maze[ny] || !maze[ny][nx]) {
                if (step) return step;
            } 

            else if (maze[ny][nx] === '.') {
                queue.push([ny, nx, step + 1]);
                maze[ny][nx] = '*';
            }
        }
    }
    return -1;
}
```

---

There are some differences/quirks here from the basic approach that was mentioned earlier in this article, but the basic building blocks are there. I don't want to drag this article on too much longer, as there's already a bit much in here, but if you'd like me to go over what exactly this code is doing, drop a comment below and I'll get to it!

---

As always, thanks for sticking around and I'll see ya in the next one 

~ ~ <3