Analyze DFS, BFS, and A* trade-offs

Consider a weighted graph with vertices $\{S,A,B,C,D,G\}$ and edges S–A(2), S–B(5), A–C(2), B–C(1), C–D(2), D–G(1), B–G(20). The heuristic values for A* are $h(A)=4$, $h(B)=3$, $h(C)=2$, $h(D)=1$, $h(G)=0$, $h(S)=5$. (1) Starting from S, give the node expansion order and the final path returned by BFS (treating edges as unweighted), by uniform-cost search, and by A* using the given $h$ (break ties alphabetically). (2) Determine and justify whether $h$ is admissible and consistent. (3) Compare the time and space complexity of DFS, BFS, UCS, and A* for this graph family (branching factor $b$, depth $d$), and describe a scenario where DFS uses less memory but is not optimal. (4) State the condition under which A* becomes Dijkstra's algorithm and show how the provided $h$ illustrates it. Overview: This question tests understanding of graph search algorithms, heuristic properties (admissibility and consistency), path optimality, and time/space complexity, by asking for application of BFS, uniform-cost search, A*, and DFS to a concrete weighted graph.