Question $1.$ Uninformed Search.

Figure $1$: Problem space

$(1)$ Draw the BFS $($Breadth$-$First Search$)$ and DFS $($Depth$-$First Search$)$ tree from S to

G$.$ You can draw them directly on the paper or write a program to simulate search processes,

showing the sequence of visited nodes and final paths.

Notice: When implementing the DFS$,$ you should try at least two different orders for

exploring adjacency nodes, such as alphabetical order and random order. And if you choose

to achieve it by code, you should ensure the code handles different adjacency node selection

orders.

$(2)$ Analyze the performance and memory usage of each algorithm in the following sce$-$

narios:

Finding a Path: Determine if there is a path between any two nodes.

Finding the Shortest Path: Identify the shortest path between two nodes in an un$-$

weighted graph.