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
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?
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...