CS2040s: Tutorial 8

BFS
Time - o(V + E)
Space- o(V)
The queue

DFS
Time - O(V + E)
Space - O(V)
The stack

BF
Time - O(VE)
Space - O (V)
Store the cost it takes to get every vertice

Q1
a) DFS Back and Forth
b) Do two bfs
One on original graph and the other on flip graph
O(2(V+E))
Space: O(V+E)


Q2
a)
Use BFS to find Naruto and to find exit
b)
O(N) for both

For bellmanford - O(N^2 * 4N^2) for time
V is n^2
E is Neighbours which is 4 beside N^2

<Use one BFS oni>
Make a copy of the graph and force the cursor to go to naruto, then add a directed arrow to the copy of the graph