def bfs(maze):
    """
    Runs BFS for part 1 of the assignment.

    @param maze: The maze to execute the search on.

    @return path: a list of tuples containing the coordinates of each state in the computed path
    """
    # TODO: Write your code here

    backtrack_dict = {}
    q = queue.Queue(maxsize=0)
    explored_list = []

    start = maze.getStart()
    q.put(start)
    backtrack_dict[start] = None   #the parent of start is none

    while (not q.empty()):
        curr_point = q.get()

        if maze.isObjective(curr_point[0], curr_point[1]):
            path = []
            path.append(curr_point)
            parent = backtrack_dict.get(curr_point)

            while (parent != None):    #loop through each point in path getting the previous point
                path.append(parent)
                curr_point = parent
                parent = backtrack_dict.get(curr_point)

            path.reverse()   #flip the list to start from start
            print(path)
            return path

        else:      #if the point is not the final goal
            if curr_point not in explored_list:
                explored_list.append(curr_point)
                neighbors = maze.getNeighbors(curr_point[0], curr_point[1])
                for neighbor in neighbors:
                    if neighbor not in explored_list:
                        q.put(neighbor)
                        backtrack_dict[neighbor] = curr_point


    return []