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)]