4. [1.5 pts] Figure 3 shows a stage graph with 9 states. Create a search tree (using Depth First Search (DFS) algorithm showing in Figure 5) to traverse the state graph from a. a. Show complete DFS search three with at least three levels (root, 1st, and 2nd). 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.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.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.5 pt].

123456789S.push(w)procedureDFS-iterative(G,v):letSbeastackS.push(v)whileSisnotemptyv=S.pop()ifvisnotlabeledasdiscovered:labelvasdiscoveredforalledgesfromvtowinG.adjacentEdges(v)do \begin{tabular}{|l|l|l|l|} \hline Fringe & Node visited & Fringe Size & Search depth \\ \hline & & & \\ \hline \end{tabular}