SECTION $2-$ Graph Algorithms

Based on the textbook algorithms, show each step for the corresponding instance by indicating

$-$ In a graph$/$tree the colors of the vertices on that step $($in step $1$ they are all white$).$

$-$ In the corresponding data structure, the discovered vertices.

$-$ Additionally use a "visited" array to indicate the visited vertex in the corresponding step.

Instance $1$: Start is $"$S$"$

Note: As a tiebreaker, use alphabetical order for adjacent vertices when placing them in the data structure, so that the one that is "visited" first is the one that appears first in the ASCII table.

Instance $2$:

Note: Label each vertex as the concatenation of rowcol, note that the cell in the upper left corner is cell $11.$ The sequence for including adjacent vertices must be south, east, west, north $($if you follow another sequence the exercise will result in several errors in your answer, even if the steps of the algorithm are correct, points will be deducted if you do not follow these instructions$).$

$-$ The search stops when the goal vertex $\backslash (($G$)\backslash )$ is found.

$3.$ BFS $(3$ points$)$

Instance $1$

$(1\mathrm{.}5$ points$)$

Graph

Instance $2$

$(1\mathrm{.}5$ points$)$

Graph or Tree

$4.$ DFS $(3$ points$)$

Instance $1$

$(1\mathrm{.}5$ points$)$

Graph

Instance $2$

$(1\mathrm{.}5$ points$)$

Graph$/$Tree

Data structure

Data structure

Visited

Visited