Consider the following problem for path finding where $S$ is the source,

$(8$ marks$)$

G is the Goal and O are obstacles. We can only move horizontally and

vertically $($not diagonally$).$ We will not re$-$visit an already visited cell.

Simulate the application of Breadth$-$first search tree to find all

paths from S to G$.$ Provide the order of visit for each node. $[4$

marks$]$

Simulate the application of Depth$-$first search tree to find all

paths from S to G$.$ Provide the order of visit for each node. $[4$

marks$]$