Data Structures BFS Breadth First Search algorithm improvement written in python

Question

I have written a python program that calculates the traversal of BFS, but it seems inefficient to me for few reasons like

1. I have to say, how many nodes there will be at the start
2. I'm not satisfied with the node assigning technique

How to make it more efficient that is my question?

from __future__ import print_function
class graph(object):
 def __init__(self, n):
 #initiating a 2d array for the graph
 self.graph = [[] for y in range(n)]
 #al the alphabet characters ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 
 # 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z']
 self.alphab = [chr(97+i) for i in range(26)]
 def addnode(self,u,v):
 #populating the 2d array with the graph
 self.graph[self.alphab.index(u)].append(self.alphab.index(v))
 #printing the graph if needed
 def printgraph(self):
 print('\nthe graph structure is {}\n'.format(self.graph))
 def bfs(self, node):
 node = self.alphab.index(node)
 print('\nstarting from node {} the traverse is '.format(self.alphab[node])) 
 queue = []
 visited = [None for i in range(len(self.graph))]
 parent = [None for i in range(len(self.graph))]
 distance = [0 for i in range(len(self.graph))] 
 queue.append(node)
 visited[node] = True
 while len(queue) != 0:
 node = queue[0]
 del queue[0]
 for i in self.graph[node]:
 if visited[i] == None:
 queue.append(i)
 visited[i] = True
 distance[i] = distance[node] + 1
 parent[i] = node
 #converting them back to ascii when printing using the list we created
 print('--->', self.alphab[node],)
 print('\nthe distance structure is {}\n\nand the parents structure is {}'.format(distance, [ self.alphab[i] if i != None else i for i in parent ]),)
def main():
 #How many nodes there will be initiating with the constructor
 se = graph(4)
 """
 a----b.
 | . 
 |. 
 c----d """
 se.addnode('a', 'b')
 se.addnode('a', 'c')
 se.addnode('b', 'c')
 se.addnode('c', 'a')
 se.addnode('c', 'd')
 se.addnode('d', 'd')
 se.printgraph()
 se.bfs('a')
if __name__ == '__main__':
 main()

the output for starting from node 'a'

the graph structure is [[1, 2], [2], [0, 3], [3]]
starting from node a the traverse is 
---> a
---> b
---> c
---> d
the distance structure is [0, 1, 1, 2]
and the parents structure is [None, 'a', 'a', 'c']

Answer 1

The very first thing that caught my eye was the del queue[0] which is a \$O(n)\$ operation since it requires for the whole list to be moved.

There is a quick win here - use collections.deque() which has a .popleft() method operating at \$O(1)\$:

queue = deque([node])
while queue:
 node = queue.popleft()
 for i in self.graph[node]:
 if visited[i] is None:
 queue.append(i)
 visited[i] = True
 distance[i] = distance[node] + 1
 parent[i] = node

where deque is imported this way:

from collections import deque

Also note the use of while queue: instead of a less efficient and less readable while len(queue) != 0:.

---

There is a number of code style issues as well:

• look for the PEP8 violations, in particular:
  • class name should start with a capital letter - Graph instead of graph
• use proper documentation strings instead of regular comments before the method definitions
  • watch for the spaces around operators and the use of blank lines

• _ (underscore) variable name is agreed to be used a throwaway variable name, e.g.:

  self.graph = [[] for _ in range(n)]
  

  instead of:

  self.graph = [[] for y in range(n)]
  

• Shantanu Bedajna: thanks sir for the feedback :) i will keep in mind the things you mentioned, i didn't knew about the del queue[0] part you mentioned, thanks for the help.