# Topic 9 Exercises

## Exercise 1

#### Modfied BFS Description:
Parameters:
v1, our inital vertex
v2, the vertex we would like to reach
Implementation:
* Create two queues:
* routes: Holds arrays containing the routes (all routes will orginate at v1)
* toCheck: Holds vertices to visit, will have a flag (ie null) to tell the routes queue to move to the next route when we are done processing the edges of the current vertex
* Start at our inital vertex v1
* Load all of v1's edges into the toCheck queue, followed by a null. At this point our queues would appear as:
* routes: [v1]
* toCheck: v1-e1,v1-e2,null (assuming v1 has 2 edges)
* Now we being to iterate through the toCheck queue
* First we pop the first route in the routes queue
* Next we pop each vertex in the toCheck queue and add it to the curent route and push it to the roots queue
* Then we add each of the current vertex's edges into the toCheck queue followed by a null flag
* At this point our queues look like:
* routes: [v1-e1,v1],[v1-e2,v1]
* toCheck: v1-(v1-e1), v2-(v1-e1), null, v1-(v1-e2), v2-(v1-e2), null
* We continue this process of adding vertices to the toCheck queue and the path to them to the routes queue until we either
* Find that one of the vertices is v2, at which point we have found a path between the two.
* If the number of moves from v1 to v2 is even, then we know this is the shortest path and we can return the number of moves / 2 as the coins will be moving at the same time and converge on the midpoint of the path
* If at this point the current route contains v2 twice we can eliminate it as it has already gone through at a cycle if one exists and it will be impossible for this route to result in any minimum
* Find that there is not path between the v1 and v2
* We will know this when
* Either our routes queue is empty becasue we cannot reach v2 in an even number of moves even with cycling through vertices more than once
* Or that every route in our routes queue contains v1 for at least three times. This means that there is no possible way to reach v2 from v1 and thus there will never be any path between the two

#### Using our modifed BFS for this problem:
Initially we have the vertices of the two coins as v1,v2.
* If if v1 == v2, then we return 0 as they are already at the same vertex without moving.
* Else, now we must search through the vertices to determine if there is a series of moves that will bring the two coins to the same spot. We will use a breadth first seach to find the minumum distance requried if possible. Choose one, v1 or v2 and begin a modified BFS through all their respective edges (we will choose v1 but doesn't matter which one is chosen)
* Use our algorithim defined above to get the shortest route, or find that none exists

## Exercise 2
#### Algorithim:
##### Parameters:
Vertex v1, aribtrary vertex
Graph g, the undirected graph we are attempting to make into a directed graph
* Start a depth first seach at v1
* Iterate down one path marking each edge as taken after we use it.
* Since we know what vertex we came from, we must choose a differnet edge to take to the next vertex
* If we reach a vertex that has no edges to uses (all vertices reachable have already been used) and is not v1, then we move back until we find a path that we have not taken, however we will keep track of these paths
* If we end up reaching v1 on our move back and all possible edges have been ~~tried~~ included in the DFS tree, then there is no solution
* or if we find that a vertex has no edges except one pointing to the previous vertex, then there is also no solution as we cannot make a cycle with a vertex with only one edge
* if we reach v1 (via some back edge) we can evaluate the path
* if it includes all vertices then we know that we have a solution
* else we continue our depth first search
* if we reach the end of our inital depth first search without finding any solutions then we will look at the solutions that reached the en