I have written a python program that calculates the traversal of BFS, but it seems inefficient to me for few reasons like
- I have to say, how many nodes there will be at the start
- 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']