Apply the Breadth$-$First Search $($BFS$)$ algorithm to find a path from vertex $S$ to vertex $T$ in the given graph. In addition to the final path, you are also required to list the order in which nodes are expanded. $($Assume lexicographic ordering when there are several choices$)(5$ points$)$

Apply the Depth$-$First Search $($DFS$)$ algorithm to find a path from vertex $S$ to vertex $T$ in the given graph. In addition to the final path, you are also required to list the order in which nodes are expanded. $($Assume lexicographic ordering when there are several choices$)(5$ points$)$

In the given graph, the number next to each edge is the cost of the performing the action corresponding to that edge. Apply the Uniform$-$Cost Search $($UCS$)$ algorithm to find a shortest path from vertex $S$ to vertex $T.$ In addition to the final path, you are also required to list the order in which nodes are expanded. $($Assume lexicographic ordering when there are several choices$)(5$ points$)$

In the two given graphs, the number next to each edge is the cost of the performing the action corresponding to that edge. The number next to each vertex is the heuristic cost. Apply A$*$ Search algorithm to find the shortest path from vertex $S$ to vertex $T.$ In addition to the final path, you are also required to $1)$ list the order in which nodes are expanded, $2)$ describe the concrete calculating and exploring steps $($Assume lexicographic ordering when there are several choices$)(5$ points $+5$ points$)$