Is this breadth-first search correct?

Question

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


def breadth_first(maze, x, y):
    queue.append((x, y))
    visited.append((x, y))

    while queue:
        pos = queue[0]
        x = pos[0]
        y = pos[1]

        # 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)

            # add to queue
            if len(maze[0]) > 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


closest = breadth_first(m, 0, 0)

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[1]][pos[0]] = '+'

    return maze


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

Answer 1

• The code uses pos=queue[0] 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[0]) 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.