Breadth-First-Search short tutorial
Welcome to my second article on AI algorithms. If you have not learned DFS, check out https://medium.com/@tingyan.deng/depth-first-search-short-tutorial-165b41f1b1c0 on my short tutorial.
In this story, we focus on Breadth-First-Search, BFS, and show some examples on how to apply it.
BFS uses the opposite strategy as a DFS, which instead explores the node branch as far as possible before being forced to backtrack and expand other nodes.
In the example graph above, BFS will search a node depth-by-depth. For example, if we are looking for the node 6. BFS will first scan the level 1, which only has the node 1. Then it will go down to 2,7,8, which also does not contain 9. It will then go to the third level 3,6,9,12 to find 9, the desired number.
Now let’s run BFS on the directional weighted graph below to gain more insights on how it works.
The BFS is commonly used in graphs like this in the field of artificial intelligence and understand the steps is crucial for a good foundation of AI methods. The number on the edges here are weights. Now let’s define an important concept in AI: fringe.
fringe: a data structure used to store all the possible states (nodes) that you can go from the current states.
Since this problem is more complicated than the simple binary search tree, I will be using a more systematic approach to solve it. We will need to first write a list of current nodes and use a priority queue for the fringe.
When we first start the problem, our current node is N/A and the fringe is S(start). Below each node, we need to write done the depth of this node because algorithms like BFS depends on the depth as it wants to go to the node that has the smallest depth number before backtracking. In the beginning, we have {S(0)} as it takes 0 steps or it’s depth 0 to get to the starting node in the fringe
Now we pop our element in the fringe to the current node. From our current node S, we can go to the nodes A, B, C. Thus, in this step, our current node is S(0) and fringe is {A(1), B(1), C(1)}. Since all of the nodes in the fringe has the same depth, we will go by alphabetical order and pop A(1) as our next current node.
Now for current node A(1), our fringe is {B(1), C(1), E(2)} as we add E(2) to our fringe list. Next, BFS will go the node that has the smallest depth, and by alphabetical order, we will pop B(1) as our current node.
For current node B(1), we can go to node C(2) and adding this node into the fringe, now we have {(C(1), E(2), C(2)}. Notice here C(1) and C(2) represent two different way to approach the node C, and we leave both of them here because there are both unvisited. Then, we pop off C(1) from the fringe.
For current node C(1), we add D(2) and G(2) into the fringe, giving us {E(2), C(2), D(2), G(2)} and we eliminate C(2) from our list because C is visited already, which gives us {E(2), D(2), G(2)}.
Now I believe you got the idea (it’s OK if not:), walk through it one more time) and you should try to finish this problem by finding a path from start to goal on your own and check back for the answer.
SOLUTION: Now by alphabetical order, we pop off D(2) and has the fringe {E(2), G(2), G(3)}. Then wee pop off E(2) and has the fringe {G(2), G(3), D(3)}. Now we just pop G(2) to get our goal node.
We can track the path by going back to the fringe and explore we got each current node in our steps as shown in the graph below. We first check which current node added G(2) as a fringe and then track which current node added that current node as a fringe. Here, our path is S->C->G
Now as you have already read through the problem, try to mimic the whole solution on your own and check back if you have any questions.
Note: The BFS only looks at the depth level like the DFS, and it ignores the weight. I purposefully wrote the weight on the graph to confuse you (or make you remember :))
BFS is a very important algorithm along with other algorithms like DFS, A*, etc.. Read my other articles about DFS and how it compares and contrasts with DFS.
Please contact me tingyan.deng@vanderbilt.edu if you have any questions.
