Algorithm

Let's first go through the algorithm:

1. Transform the edge list into an adjacency list.
2. Perform either a Depth-First Search or Breadth-First Search through the graph.
3. Maintain the destination vertex as constant and update the source vertex as you traverse the graph.
4. If the source vertex matches the destination vertex at any point during traversal, return true.
5. If the search concludes without finding the destination vertex, return false.

Walkthrough I

Let's do a walkthrough using the graph below. We'll perform DFS with recursion.

Step 1: In the first step, we'll convert the edge list into an adjacency list. You can see how to transform an edge list into an adjacency list in this assignment.

Step 2: Next, we'll perform a depth-first search using recursion, updating the source vertex as we traverse the graph. Like previous walkthroughs, we'll visually keep track of our neighbor vertices in orange next to each function call. In the first function call, the source is 1 and the destination is 4. Since they are not the same, we add 1 to the visited set and call dfs again, passing the first neighbor of vertex 1, which is vertex 2, as the new source vertex, while keeping the destination vertex the same.

Step 3: In the second function call, the source is 2 and the destination is 4. Since they are different, we add 2 to the visited set. The first neighbor of 2 is the vertex 1 which we skip since it is in the visited set. Consequently, we call dfs passing the second neighbor of vertex 2, vertex 3, as the new source vertex while keeping the destination vertex the same.

Step 4: In the third function call, the source is 3 and the destination is 4. Since they are not the same, we add 3 to the visited set. The only neighbor of vertex 3 is already in the visited set (vertex 2), meaning we can return from this function and pop it from the stack. Just because we've returned false for this function call doesn't mean there doesn't exist a path, it just means that there isn't a path from this source node, 3, to our destination, 4, that without going through a node we've already visited, 2. We could get to our destination with a path like, 1 -> 2 -> 3 -> 2 -> 4, but using a visited set avoids us needlessly exploring paths like this, or worse, from getting stuck in a cycle.

Step 5: We are back in the second function call, where we have already called dfs with the first neighbor, then with vertex 3, and now we will check the third neighbor, vertex 4.

Step 6: In this function call, the source vertex equals the destination vertex, so we return true. This causes a bubble-up effect where the function call dfs(adjList, 2, 4) subsequently returns true, as there is a path from 2 to 4 which causes the first function call dfs(adjList, 1, 4) to return true, as there is a path from 1 to 4.

Walkthrough II

Let's do another walkthrough where the path doesn't exist.

Step 1: In the first step, we'll convert the edge list into an adjacency list.

Step 2: Next, we'll perform a depth-first search using recursion. In the first function call, the source is 1 and the destination is 4. Since they are not the same, we add 1 to the visited set and call dfs again, passing the first neighbor of vertex 1, which is vertex 2, as the new source vertex, while keeping the destination vertex the same.

Step 3: In the second function call, the source is 2, and the destination is 4. Since they are different, we add 2 to the visited set. The first neighbor of 2 is the vertex 1 which we skip since it is in the visited set. Consequently, we call dfs passing the second neighbor of vertex 2, vertex 3, as the new source vertex while keeping the destination vertex the same.

Step 4: In the third function call, the source is 3 and the destination is 4. Since they are not the same, we add 3 to the visited set. The only neighbor of vertex 3 is already in the visited set (vertex 2), meaning we can return from this function and pop if from the stack.

Step 5: Back in the second function call, we have visited all neighbors; thus, the iteration completes and we return from this function as well. Finally, in the first function call, having visited all neighbors without returning true, we return false from the function and pop it from the stack. We've explored all paths, and none of them lead to 4.