Breadth First Search
Ghost In The Machine
You ever play Pacman as a kid and wonder if its just randomness associated with the ghosts chasing you down? or if there is a method behind all this madness. Enter BFS(Breadth First Search), this algorithm traverses thru a tree or graph data structure, starting at the tree root or node on a graph and explores all the neighbor nodes at that depth before moving on to the next layer of nodes. This is the essence of the ghosst in Pacman, these ghosts are using BFS to traverse down nodes, before moving on to the next layer of nodes, ultimately to find a way to kill Pacman. Brutal.
Truth Is In The Name
As mention before, when doing a BFS we are searching thru each node, layer by layer, giving truth to the name. This search is done by putting each node in a queue, this is what keeps track of each node, and remembers each node thru the continuation down the tree or graph until completion.
Pseudo Code
Depending on what your search parameters are your code will vary, however here below is a snip it of some pseudo code to give an idea of how to go about traversing thru your tree or graph.
procedure BFS(G, root) is
let Q be a queue
label root as discovered
Q.enqueue(root)
while Q is not empty do
v := Q.dequeue()
if v is the goal then
return v
for all edges from v to w in G.adjacentEdges(v) do
if w is not labeled as discovered then
label w as discovered
Q.enqueue(w)https://en.wikipedia.org/wiki/Breadth-first_search
A good use case for BFS would be using it to help find the shortest path using Dijkstra’s algorithm. Dijkstra’s algorithm helps find the shortest path between one node and every other node. It also can be used to help find the shortest path from a single node and a single destination node by stopping the algo once the shortest path has been determined.
Thats it! quick look at BFS and its adaption into Pacman! Below is more material worth checking out get more in-depth graphs and videos.
Happy Coding!
- WilliamFiset — Youtube
- HackerEarth
- TutorialsPoint
