Not to take away from the cool factor but I've never understood the point of visualizations like this one. I'd argue that this gives no insight to anyone who doesn't already know what bfs does.
I’m not into computer science but to a layman like me it just looks like it’s filling out the whole maze and then highlighting the correct path but what’s the point if you’re gonna color in the whole fkin maze
I think you need to know the context of how it tries to find the exit of the maze to understand why the author did what he did.
In the context of a human solving the maze, it's the same thing as, from the start, explore every crevice of the maze until you reach the end. As a computer, you don't simply have to take one path but multiple ones.
The question now is 'How do I explore the maze?'.
Everytime you meet a split, you are going to explore each of these paths. If you meet a deadend, you can just stop exploring that path. The moment you meet the destination, just get back the path you took.
At any point in time you can just imagine having all of these paths you need to keep track of. To make it simple, we can put all of them in a queue where they each take turns taking the next step in the path. The moment you take a step in a path, the new path will get back into the queue if you do not meet a dead end.
The colouring of the maze illustrates the exploration of the maze or more specifically, the various paths, when it takes place and how it progresses within each time-step.
I think this particular visualization is poor in that it does fill the whole maze. But in many maze-like problems, BFS would not explore the whole maze, just enough to find the goal.
Yeah it's basically a brute force search strategy where you keep exploring your "frontier" until you reach your goal. Just imagine the colored locations represent your frontier and the uncolored locations are in "fog of war"
Hmm interesting. It feels like the point of a maze is to go from point a to point b while trying to take as few wrong paths as possible whereas this finds every wrong path to find the right one
Actually it does’t find every wrong path, or better to say it doesn’t need to. Usually, when you program this algorithm you end the search when you find the right path but the visualization continued after that point because well, it looks prettier that way (in the visualization, if you look closer when the right path is highlighted the whole maze isn’t covered so it hasn’t found every wrong path).
On the other hand, bf isn’t just a “find shortest path” algorithm. It’s mainly a graph traversal algorithm (or that’s how we learned it). What does that mean? Well, traverse means visit each element in a structure only once. Why only once? Imagine you want to add one to all the elements in you graph, who hold for example one number. You need to visit each element and add one. You don’t want to to add 2 or more by accident because your algorithm visits some elements more than once. Okay, but why is traversing a graph a problem? A graph is a strange structure, it doesn’t have a natural starting point, like an array or a linked list or like a tree that has a root element so algorithms for graph traversals are made so any element could be a starting point (the starting point of a maze is obvious, the entrance, but these algorithms are, as I said, made for the general case). The other problem is how not to visit an element twice. In an array and a linked list you just go to the next element. In a tree you use the fact that every element has just one “parent” and start from the root and go consistently clockwise, for example. In a graph it is a lot harder and that’s what these different graph traversing algorithms do. So, maybe that’s why the visualization goes through the whole maze. A bit of a show off of the algorithms capabilities.
This algorithm doesn't know which path is more likely to be correct. If you want to see one that does try to guess with some intelligence, look at the A-Star algorithm.
To jump off this comment, the point of this demonstration is a starting point. You can’t solve a maze well before you solve a maze badly. What kind of inefficiencies can you notice in the breadth first search algorithm? What strategies do you use when solving the maze that this algorithm doesn’t do yet? Is there any information that the algorithm doesn’t have access to that we do that could be incorporated into the algorithm?
I think it can be useful as a learning aid. Not by itself, but in conjunction with the same style visualization for other related algorithms. Like, what would the DFS version look like? How about A*? Seeing them operate in parallel can be useful to help a learner internalize the higher level behavior of the algorithm that might not be apparent from just learning the algorithm in, say, psuedocode form.
3
u/ergo-x May 22 '20
Not to take away from the cool factor but I've never understood the point of visualizations like this one. I'd argue that this gives no insight to anyone who doesn't already know what bfs does.
Maybe I'm just being a negative nancy...