# Is this breadth-first search correct?

I wrote a program that is supposed to be a breadth-first search algorithm, but I'm very new to search algorithm so I don't know if my method is very effective or if there is a simpler way to do this. So I'm asking if there is a way to improve my code.

In this case, I have made the program search for the closest 1 in a 2d list where you can enter the start position and it will then find the shortest path between the start position and the 1. Of course, this can be changed in a variety of ways.

I tried to make the variables and function names as clear as possible, so I don't think I need to explain everything about my code, but that's easy for me to say so please comment if you need clarification.

m = [[1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0],
[0, 0, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 1],
[0, 0, 0, 0, 1, 0],
[1, 0, 1, 0, 0, 0],
[1, 0, 0, 0, 0, 1],
[0, 0, 0, 0, 1, 0],
[1, 0, 1, 0, 0, 0]]

visited = []
queue = []

parent = {}
num = 0

queue.append((x, y))
visited.append((x, y))

while queue:
pos = queue
x = pos
y = pos

# remove from queue
queue.remove(pos)

# find neighbor
for dir_x, dir_y in ((-1, 0), (1, 0), (0, -1), (0, 1)):
newx = x + dir_x
newy = y + dir_y

neighbor = (newx, newy)

if len(maze) > newx >= 0 and len(maze) > newy >= 0 and neighbor not in visited and neighbor not in queue:
if m[newy][newx] == 1:
parent[neighbor] = pos
return neighbor

queue.append(neighbor)
visited.append(neighbor)
parent[neighbor] = pos

path = [closest]

def search(traceback):
while traceback != (0, 0):
for key, value in parent.items():
if traceback == key:
path.append(value)
traceback = value

return path

def solved(maze, input_path):
for pos in input_path[1:-1]:
maze[pos][pos] = '+'

return maze

print(solved(m, search(closest)))

• Welcome to cod review where we review working code and provide suggestions on how the code can be improved. The title may indicate that you don't know if the code is working or not. Does the code do what it is supposed to do? Can you clarify the question a little bit more. Jan 4, 2020 at 17:02
• @pacmaninbw It does what it is supposed to do, but I would like suggestions on improvements Jan 4, 2020 at 19:25

• The code uses pos=queue and queue.remove(pos). Instead, you could use pos=queue.pop(0). Be aware that popping from the front isn't really efficient, it's O(n), which is bad for big lists.

• You could use the fact that you can assign to two variables at once: x, y = queue.pop(0). This removes pos completely, fewer variables are easier to understand.

• You pass a maze and the start position to the BFS. However, the queue and others are global. That's very bad design. Keep things in as small a scope as possible. You can always return a tuple from a function if a single value is not sufficient, if that was the reason.

• What are len(maze) and len(maze)? Call those width and height and compute them at the start of the function to answer that question.

• The if-clause in the loop has too many conditions at once, which is really hard to read. There's nothing wrong with a continue when the computed position was already visited, just to illustrate one check that could be extracted.

• parent[neighbor] = pos is done at two places. Do that exactly once when you first visit a new place.

• visited seems to be the list of places that were already visited. The type is a Python list, but a set would be a more suitable datatype for that, unless the order of the elements matters.