Algorithms For Dummies

  Reconnecting the Dots 

     177

steps = bfs(graph, 'A')

print ('\nBFS:', steps)

Queue is: ['A']

Processing A

Adding B to the queue

Adding C to the queue

Queue is: ['B', 'C']

Processing B

Adding A to the queue

Adding D to the queue

Queue is: ['C', 'A', 'D']

Processing C

Adding E to the queue

Queue is: ['A', 'D', 'E']

Processing A

Queue is: ['D', 'E']

Processing D

Adding F to the queue

Queue is: ['E', 'F']

Processing E

Queue is: ['F']

Processing F

BFS: ['A>B', 'A>C', 'B>A', 'B>D', 'C>E', 'D>F']

The output shows how the algorithm searches. It’s in the order that you expect — 

one level at a time. The biggest advantage of using BFS is that it’s guaranteed 

to return the shortest path between two points as the first output when used to 

find paths.

The example code uses a simple list as a queue. As described in Chapter 4, a queue 

is a first in/first out (FIFO) data structure that works like a line at a bank, where 

the first item put into the queue is also the first item that comes out. For this pur-

pose, Python provides an even better data structure called a deque (pronounced 

deck). You create it using the 

deque

 function from the 

collections

 package. It 

performs insertions and extractions in linear time, and you can use it as both a 

queue and a stack. You can discover more about the 

deque

 function at 

https://

pymotw.com/2/collections/deque.html

.