Breadth-First-Search (BFS) in Python for Path Traversed and Shortest Path Taken

Question

I tried implementing a bread-first search algorithm a lot, but I just don't get it right. The start node is S and the goal node is J. I'm just not getting J at all.

This is the code that I'm using for printing the path being traversed, but I also need to find the shortest path:

graph = {
  'S' : ['A','B', 'C'],
  'A' : ['D'],
  'B' : ['E'],
  'C' : ['F', 'J'],
  'D' : ['G'],
  'E' : ['I', 'J'],
  'F' : ['S'],
  'J' : [],
  'G' : ['H'],
  'I' : [],
  'J' : [],
  'H' : ['D']
}

visited = [] # List for visited nodes.
queue = []     #Initialize a queue

def bfs(visited, graph, node): #function for BFS
  visited.append(node)
  queue.append(node)

  while queue:          # Creating loop to visit each node
    m = queue.pop(0) 
    print (m, end = " ") 

    for neighbour in graph[m]:
      if neighbour not in visited:
        visited.append(neighbour)
        queue.append(neighbour)

# Driver Code
print("Following is the Breadth-First Search")
bfs(visited, graph, 'S')    # function calling

Answer 1

You'd need to tell your BFS function what your target node is, so that the BFS traversal can stop as soon as that target node is encountered.

Some other comments:

• Your dict literal has a duplicate key 'J' — you should remove it.

• visited and queue only serve a single BFS call, and should start from scratch each time a BFS search is launched. So these should not be global names, but be defined in the scope of the function only.

• You print the nodes as they are visited, but this does not represent a path. It represents a level order traversal of the graph. So don't print this. Instead have the function return the path (see next point).

• The list visited is used to avoid revisiting the same node again, but it doesn't give you any information about how we got to a certain node. You could transform visited into a dictionary. Then, when you mark a node as visited, mark it with the node where you came from. This way you can reconstruct a path once you have found the target node — you can walk backwards back to the starting node.

• You've defined queue as a list, but a list's pop(0) method call is not efficient. Instead use a deque and its popleft() method.

Here is your code with the above remarks taken into account.

from collections import deque

graph = {
  'S' : ['A','B', 'C'],
  'A' : ['D'],
  'B' : ['E'],
  'C' : ['F', 'J'],
  'D' : ['G'],
  'E' : ['I', 'J'],
  'F' : ['S'],
  'G' : ['H'],
  'I' : [],
  'J' : [],
  'H' : ['D']
}

def bfs(graph, node, target):
    # These lists should not be global. At each call of BFS, they should reset
    visited = {}  # Use a dict so you can store where the visit came from
    queue = deque()    # Use a deque to not lose efficiency with pop(0)

    visited[node] = None
    queue.append(node)
    
    while queue:
        m = queue.popleft() 
        if m == target:  # Bingo!
            # Extract path from visited information
            path = []
            while m:
                path.append(m)
                m = visited[m]  # Walk back
            return path[::-1]  # Reverse it
        for neighbour in graph[m]:
            if neighbour not in visited:
                visited[neighbour] = m  # Remember where we came from
                queue.append(neighbour)
                
# Driver Code
print("Following is the Breadth-First Search")
print(bfs(graph, 'S', 'J'))

Output:

['S', 'C', 'J']

If you want to see which nodes get visited, then you have some options:

• Show when a node is dequeued from the queue:

  Change:

  m = queue.popleft() 
  

  to:

  m = queue.popleft() 
  print (m, end = " ") 
  

  or:

• Show when a node is enqueued to the queue:

  Change:

  queue.append(neighbour)
  

  to:

  queue.append(neighbour)
  print (neighbor, end = " ") 
  

  and change:

  Change:

  queue.append(node)
  

  to:

  queue.append(node)
  print (node, end = " ") 
  

The output is slightly different, and it depends on what you call "visited". The second one will output two more nodes that will never be popped from the queue.

To separate the output of the visits from the output of the path, just print a newline character with print(). So, in the driver code do:

path = bfs(graph, 'S', 'J'))
print()  # Extra print to start a new line
print(path)