Part $1$: Giving that, after applying Depth$-$first search $($DFS$),$ the visited nodes are as follows:

A$-$B$-$E$-$F$-$G$-$C$-$H$-$D$-$I$-$J

Assuming the order of the nodes are in alphabetic order ABC, and the starting node is $A$ :

Draw the graph tree for this problem. $(5$ points$)$

Visit all the nodes using the Breadth$-$first search $($BFS$).(5$ points$)$

If the goal is to reach node G from node A $,$ show the solution after applying both BFS and DFS and show which algorithm is faster. $(5$ points$)$

$[$Total: $15]$

Part $2$: From the figure $1,$ the goal is to reach the node G from the start node S$.$

Giving that, if you are visiting node $A,$ the estimated heuristic value from $A$ to $G$ is $h(G)=20,$ and the cost value from node $A$ to node $S$ is $g(S)=10.$

Apply the $A^{**}$ heuristic algorithm to find the best path from S to G $.($show all the steps$).(5$ points$)$

Solve this problem using Greedy algorithm. $(3$ points$)$

Compare between the two solutions.

Build the search tree and apply the Depth$-$first search. $(7$ points$)$

a$.$ The node should appear just one time.

o$.$ The expanded nodes should be in order $($i$.$e$.,$ from $S,$ the children will be ordered A then $B,$ and from A the children will be $C$ then $D)$

$[$Total: $15$ points$]$

Part $3$: Compare between the uninformed search and the informed search. $(5$ points$)$