In Graph Search algorithms, the visited nodes are recorded so they will not be visited again. Please run these algorithms on the state space graph below, where the initial state is S, the goal states are G1, G2 and G3, the step costs are edge labels. The heuristic function is given in the right-hand-side table. Note: the graph has directed edges! 6 State h(n) S D 2 S 5 5 9 6 7 E B 3 B C 4 F A D 6 8 9 5 0 G2 G3 F 6 G1 For each algorithm below, please show (1) which of the three goal states (G1, G2, and G3) is reached first, and (2) what is the sequence of expanded" nodes (the sequence until a goal state is reached). Note: a node is considered expanded when it is removed from the fringe (in the graph search pseudo code you are familiar with). Note:use alphabetic order as tie-breaker (given equal cost in the priority queue, expand alphabetically). IMPORTANTI: When you enter the sequence, drop all spaces or other delimiters. For example, the sequence S, A, B, C, G2 should be entered SABCG2 (a) Uniform cost search if- g) Goal reached - G2 Sequence of expanded nodes = (b) Greedy search (f = h) Goal reached = G1 Sequence of expanded nodes = (C) A+ search (f = g + h) Goal reached G3 Sequence of expanded nodes