Part A

You are given a graph representing a network of cities connected by roads. Each node represents a city labeled A through L$,$ and the edges represent roads with associated travel costs $($shown as numbers on the edges$).$ The goal is to find the least$-$cost path from Start City A to Goal City $\backslash (\backslash$mathbf$\{$L$\}\backslash ).$ Additionally, heuristic values are provided $($in red$)$ to use for the below questions as needed. For BFS and DFS$,$ visit the successors in alphabetical order. For UCS and A$*,$ break ties for visiting successors in alphabetical order.

$1.$a$.$i$.(1$ pt$)$ Breadth$-$First Search $($BFS$)$: What is the path that BFS returns from the start to the goal? Also, list the order in which nodes are visited starting from node A to reach the goal node L using BFS$.$

Visited Nodes: X$,$ Y$,$ Z$,...$

Path: X$,$ Y$,$ Z$,...$

$1.$a$.$ii$.(1$ pt$)$ Depth$-$First Search $($DFS$)$: What is the path that DFS returns from the start to the goal? Also, list the order in which nodes are visited starting from node A to reach the goal node L using DFS$.$

Visited Nodes: X$,$ Y$,$ Z$,...$

Path: X$,$ Y$,$ Z$,...$

$1.$a$.$iii. $(1$ pt$)$ Uniform Cost Search $($UCS$)$: What is the path that UCS returns from the start to the goal? Also, list the order in which nodes are visited starting from node A to reach the goal node L using UCS.

Visited Nodes: X$,$ Y$,$ Z$,...$

Path: X$,$ Y$,$ Z$,...$