Consider the following graph. $S$ is the start state and $G$ is the goal state. Edges are annotated with their cost.

For each of the following search strategies, give $(1)$ the solution path that will be returned, or write none if no path will be returned; $(2)$ the frontier list, and $(3)$ the explored$/$extended nodes in the order expanded. If there are ties, assume alphabetical tiebreaking $($i$.$e$.,$ nodes for states earlier in the alphabet are expanded first$).$

A$)$ BFS

Solution:

Frontier:

Explored:

B$)$ DFS

Solution:

Frontier:

Explored: