One 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!
This representation of a typical BFS was created by Reducible on YouTube and I highly recommend checking them out and giving them a sub. Reducible's video 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).
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 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. 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:
While 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 challenge. This solution was NOT my own work, just to clarify. This incredibly elegant solution was done by Maxim and it is a thing of beauty. And without further ado, here is the solution:
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
Top comments (0)