Breadth First Search (BFS)
Breadth first search is an algorithm to visit the nodes of a graph or a tree.
In BFS, we use a queue to track the nodes that we need to visit, and a hash table to track nodes we've visited.
Starting at the root node, we add all neighbor nodes to the queue, as long as they have not been visited.
The node is then considered processed, so we don't need to explore that node further.
We pop the next node from our queue, and repeat the process until the queue becomes empty, at which point we've explored the entire graph.
Traverse a graph
Step through the graph below and see how nodes become visited (marked in gray).
Breadth first search in Python
Given a graph as an adjacency list, here's how we visit its nodes through BFS.
Remember, the Python utility
collections.deque()is used to model a queue, and a
setto model a hash table for tracking visited nodes.