bfs&a*

def breadthFirstSearch(problem):
    """Search the shallowest nodes in the search tree first."""
    "*** YOUR CODE HERE ***"
    frontier = util.Queue()
    explored = []
    firstNode = Node(problem.getStartState(), None)
    frontier.push(firstNode)

    while not frontier.isEmpty():
        current = frontier.pop()
        if problem.isGoalState(current.getState()):
            path = []
            while current.getParent():
                path.append(current.getAction())
                current = current.getParent()
            path.reverse()
            return path
        explored.append(current.getState())
        for next_state, action, _ in problem.expand(current.getState()):
            node = Node(next_state, action)
            if next_state not in explored and node not in frontier.list:
                node.parent = current
                frontier.push(node)
    util.raiseNotDefined()



def aStarSearch(problem, heuristic=nullHeuristic):
    frontier = util.PriorityQueue()
    explored = []
    firstNode = Node(problem.getStartState(), None)
    frontier.push(firstNode, 0)

    while not frontier.isEmpty():
        current = frontier.pop()
        if problem.isGoalState(current.getState()):
            path = []
            while current.getParent():
                path.append(current.getAction())
                current = current.getParent()
            path.reverse()
            return path
        explored.append(current.getState())
        for next_state, action, cost in problem.expand(current.getState()):
            new_cost = current.getCost() + cost
            heuristicCost = new_cost + heuristic(next_state,problem)
            node = Node(next_state, action)
            node.cost = new_cost
            node.parent = current
            if next_state not in explored:
                frontier.update(node, heuristicCost)
    util.raiseNotDefined()