The gist of Breadth First Search
Our first project week is here (and it feels like a 2.5 day hackathon with the option to go home at the end of the school day)! Our class was given a list of projects to choose from and develop. I choose “Maze-Solver,” which is the creation of a bot which solves and generates a path for the solution for a given maze.
Enter Breadth-first Search:
Working on the maze bot might be one of the first times I have imparted a logic-centritic focus on Breadth First Search (BSF) algorithims themselves. In the course of writing this blog, I realized that I have been inplementing this approach in the context of reading pedigrees (genetic - family trees) and calculating the probabilities for phenotypic inheritance. After the following explanation you might recognize how BFS has applied to your life as well.
Ok, so what is Breadth First Search Algorithm (BFS), anyway? BSF is an approach for getting around a graph between points, referenced here as nodes. The goal is to navigate from a starting node to a node or nodes of interest. In my case, my graph is the actual maze itself. My starting node and node of interest are the maze’s starting point and the finish line, respectively.
The following is a succint step-wise 4 min video demonstration of the concept shared as background for the maze project.
This excerpt from Wikipedia gives an overview of it:
"In graph theory, breadth-first search (BFS) is a strategy for searching in a graph when search is limited to essentially two operations: (a) visit and inspect a node of a graph; (b) gain access to visit the nodes that neighbor the currently visited node. The BFS begins at a root node and inspects all the neighboring nodes. Then for each of those neighbor nodes in turn, it inspects their neighbor nodes which were unvisited, and so on. Compare BFS with the equivalent, but more memory-efficient Iterative deepening depth-first search and contrast with depth-first search.”
Breaking down the framework to into pseudocode:
The basic set-up:
1.We start with a starting or “root” node. (That’s “a” in the gif above).
2.We create an empty queue to save adjacent nodes of interest
3. We create another queue for nodes visited. (This will be a place to mark off visited nodes).
The workflow:
4. The root node (initial node) is used as a reference to scan/identify contingent (children) nodes. Those children nodes are added to the node queue. (Adding children to the queue is represented by the greying of nodes on the gif).
5. The root node (which is also the first current node) is then added to the visited nodes queue. (A blackened node on the gif indicates if that node has been visited). 6. If the element sought is found in this node, stop scanning and yield a result. Chances are that you will have to search further than the root node for your answer.
7. If indeed nothing of interest was found at the current node, go to the first child in the node queue that is yet to be visited
8. Repeat/ loop through the scan (step 4) through step 7 until the node of interest is reached.
9. If the queue is empty and all nodes have been visited, meaning that these are contained in the visited node queue at this point, no solution has been found.
10. If that’s not the case, back track to the parent of the current node and keep repeating that until an ancestral node with contingent un-visited node(s) is found, restart at step 4 and so on.
Adding conditions before adding adjacent nodes to a queue (on step 4) is one way of making BFS customizeable for a project. In the case of the maze, the game board was drawn from a string of pound signs (“#”) and spaces. The #’s represent maze boundaries and it’s inner walls, and the spaces indicate visitable paths or nodes. The board looks something like this, with the arrow indicates the starting node.
As part of my conditions for identifying a visitable adjacent nodes I checked that the node is NOT equal to a #. I also built in a condition for my bot so that if an adjacent node has the value of “@,” this will indicate that the maze solution is complete. At which point, the scanning is stopped and the winning path is prompted to be drawn.
When completed I will be sharing my finalized code for the maze-bot to exemplify the application of BSF in action in this post.
It is also note-worthy that more interesting real world applications for BFS and it’s more efficient versions are used in GPS navigation (mapping routes from points A to B), web-crawlers (which search the internet from one link to another), and in building social networks, like Facebook (where each person in a friends network is algorithmically treated as a node).