# BFS algorithm in python

I am working on a project that requires me to implement the BFS algorithm using Python, which I am new to.

The algorithm finishes execution of a 9 pieces puzzle (3x3), but it takes a really large amount of time to do so (5 minutes):

``````def bfs(self):

fringe = deque([])
# start it
fringe.append(self.stateObj.getState())

while len(fringe) > 0:
state = fringe.popleft()
self.visited.append(state)

# just for tracing
# self.helper.drawBoard(state)

if self.stateObj.isCurrentStateGoalTest(state):
return True

for next_state in self.stateObj.getNextStates(state):
if (next_state not in (self.visited + list(fringe))):
fringe.append(next_state)
``````

Can anybody point out what I could improve this to achieve better performance? Any practical answer is well accepted.

Solution

• The problematic part is probably this: `if (next_state not in (self.visited + list(fringe)))` This will a) create a new list from `fringe`, b) create another new list from that list and `visited`, c) iterate the entire list to see whether the next state is already in.

It seems like `self.visited` is a `list`. Make it a `set` instead, so the `in` check takes only O(1) instead of O(n). Also, in BFS you can add the elements to `visited` right in the `next_state` loop, so you don't have to check whether they are in the `fringe`, as well.

``````def bfs(self):
fringe = deque([self.stateObj.getState()])
while fringe:
state = fringe.popleft()
if self.stateObj.isCurrentStateGoalTest(state):
return True
for next_state in self.stateObj.getNextStates(state):
if next_state not in self.visited:
fringe.append(next_state)