Figure $1$

$[1\mathrm{.}5$ pts$]$ Figure $2$ shows a stage graph with $9$ states. Create a search tree $($using Breath First

Search $($BFS$)$ algorithm$)$ to traverse the state graph from $"a".$

a$.$ Show complete BFS search three with at least three levels $($root$,1^{st},$ and $2^{nd}).$ If

multiple nodes are created for same state, say $"f",$ use $f1,f2,f3,$ etc., to denote each

node $($the number corresponding to node being created$).$ Break tie in favor of node

with a lower alphabetic order, e$.$g$.,"$b$"$ has a higher priority than $"$c$".[0\mathrm{.}5$ pt$]$

b$.$ Report the order of the nodes being visited, and the Fringe structure $($report fringe

structure of each step as show in the table below$)[0\mathrm{.}5$ pt$].$

c$.$ Compare the fringe structure and explain the memory consumption of each method,

with respect to branching factor $(b)$ and the search depth $(d)[0\mathrm{.}5$ pt$].$