1. 3 points. Consider the graph below. The agent starts at node s and must reach node g. All edges are undirected, so they can be traversed in both directions (recall this is equivalent to a pair of directed edges). Apply BFS, DFS (tree search), and UCS to find a path from s to g. Use graph search except for DFS. Assume that nodes with the same priority are added to the queue/stack in alphabetical order. (This means that nodes are removed from a stack in reverse alphabetical order; also, note that s is part of the alphabet.) For algorithms that use a priority queue, also use alphabetical order to break ties when removing nodes with the same priority (e.g., (a,10) before (c,10)). Show: The order in which nodes are expanded The contents of the frontier after each expansion, in the correct order / with priorities if applicable The contents of the explored set, if applicable The solution path that is returned, if a solution is found Hint: You do not have to draw out the search tree. Also recall that nodes technically store paths instead of states, but it is fine to just write the corresponding state to denote the search node. The solution is the path stored in the final search node, not the list of states expanded. 3 2 1 2 4 1 4 b d g 3