Skip to main content
2 of 3
edited body; edited tags
alecxe
  • 17.3k
  • 8
  • 51
  • 93

Modifying list while iterating during Breadth-first search

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?