2. Get Path #

Created Tuesday 31 March 2020

Given A and B nodes. Return the path from A to B, if it exists.

• Path may not necessarily be the shortest in our algorithm.

Two paths are possible:

1. DFS Path

2. BFS Path

3. DFS - quite simple, just return a vector of the paths traversed.

4. BFS - returns the shortest path - Shortest path proof - property of BFS. Just make a diagram.

• We just run BFS and stop if we find the key or the graph ends. While checking for key.
• We check if visited has the key. If it does, then we print it, then check it’s predecessor(in the visited graph). We do this until we reach -1. Stop.

T.C same as BFS S.C same as BFS (2n)