Graph Traversal in Python: Breadth First Search (BFS)
Breadth First Search (BFS), also named as Breadth First Traversal (BFT), is one of the most fundamental graph traversal algorithms. These algorithms are widely used in logistic/delivery routing, map routing, maze path finding and so on.
The so called “breadth” is something illustrated like below: you scan B and C first but not B->D or B->E or B->F or C->F. Before you finish the “shallow layer” of the graph you can’t go further deep to other vertexs. (If you go deep first, that would be the Depth First Search)
Sepcifically, B and C are the direct subnode of A. The BFS scans through all the direct subnodes of the starting node, and goes further to the sub-subnodes of the subnodes. As shown below:
Understanding this, the next step is to impliment it in code.
The key mission now is to ensure all the subnode are scanned and then go forward. This mission is done by a data structure called “queue”, which possess the property of “First-In-First-Out” principle like this:
The “queue” structure can make sure all you scanned nodes to be pop out in the first-come-first-serve sequence. You can safely use a loop to scan through the graph and push these returned node to the queue.
Now let’s see a graph example in the form of “dictionary” so that you can put graph[‘A’] to retrive the list containing ‘B’ and ‘C’. Try it out here:
graph={
‘A’:[‘B’,’C’],
‘B’:[‘D’,’E’],
‘C’:[‘F’],
‘D’:[],
‘E’:[‘F’],
‘F’:[]
}graph[‘A’]
# this should gives you ['B','C']
The above python code represents the graph like below:
Here is the BFS implimentation in Python. The queue is a normal list but we will use the .append() and .pop(0) method to simulate it as a “queue” structure. More specifically, the .append() add element to the right of the list and the .pop(0) method take out the first element on the left of the list.
def bfs(graph,node): # node is the starting position
# graph is the graph in dictionary format
visited=[]
queue=[] visited.append(node)
queue.append(node)
while queue:
s=queue.pop(0)
for x in graph[s]:
if x not in visited:
visited.append(x)
queue.append(x)
return visitedbfs(graph,'A')
# you should get ['A','B','C','D','E','F']
Let’s go through the whole algorithm see what it does to the graph: it swallowed a graph and a node as input. The graph is a dictionary and the node is a string. It then made 2 container: one called visited to store the scanning sequence, and the other called queue to temporary store first-in-first-out node sequence.
The input node is the first node it process. For example, we put ‘A’ into it. The queue now is not empty and the while loop started. The ‘A’ was pop out immediately and feed into graph[‘A’] to retrive ‘B’ and ‘C’. These two are append to the end of the queue. Since the queue is pop out in a way of “first-in-first-out” manner, ‘D’, ‘E’, ‘F’ won’t be able to jump the queue to the front in the following while loops. In the next round while loop, it make sure ‘B’ is pop out and ‘D’, ‘E’ are injected to the queue. In the third round, ‘C’ is pop out and ‘F’ is append to the queue. The forth round ‘D’ pop out, nothing returned from graph. Next, ‘E’ pop out, ‘F’ returned again! Now we have a duplicate ‘F’ in the queue, so we need to add a check to prevent it from adding in.
Try the following examples to see the effect of the code:
graph={
'A':['C','E'],
'B':[],
'C':['B','G'],
'D':[],
'E':['H'],
'H':['D'],
'G':[]
}
bfs(graph,'A')
# you should get ['A','C','E','B','G','H','D']The graph above represents: we can easily validate its correctness by eye.
In the next articles, we will continue to discuss about Depth First Search, Dijkstra’s Search, and A* search in the similar approach. Finally we will compare these algorithms in parallel so that we have better understanding of them.
Reference links for reading:
