I am writing a function for implementing breadth-first search over a no. of nodes in a directed graph. The nodes are all numbers from 1-100. This is my implementation:
def BFS(start= 1, adj_dict= None):
level= {}
current= [start]
visible= []
lno= 0
step= 0
for ele in current:
if ele not in level:
level[ele]= lno
visible.extend(adj_dict[ele])
current.remove(ele)
if current==[]:
current= visible[:]
visible= []
lno+=1
return level
This did not work correctly and stored only the start
key in adj_dict
. I ran the debugger and saw that the code exited for loop after first iteration.
Upon searching a little about the cause of this, I found this question- https://stackoverflow.com/questions/1207406/remove-items-from-a-list-while-iterating on SO. This was the cause of error. The answers to that question suggest that I create a new list somehow, either using list comprehension or using slicing but none of them will help in my case.
So, I thought of adding a while loop to achieve the desired result. This is how it looks now:
while current:
for ele in current:
if ele not in level:
level[ele]= lno
visible.extend(adj_dict[ele])
current.remove(ele)
if current==[]:
current= visible[:]
visible= []
lno+=1
This works now. What I want to ask is this a correct way to achieve the effect or am I just getting lucky and the code can break easily? Also is this the pythonic way?