Practice: Has Path

In this assignment, you will apply your acquired knowledge to solve the "Has Path" problem.

Problem Description

// Given an undirected graph represented by an edge list, determine if
// there is a path between specified source and destination vertices.

// Implement the function `hasPath` that takes three arguments:
// an edge list representing the graph, a source vertex, and a
// destination vertex. The function should return true if a path
// exists between the source and destination, and false otherwise.

function hasPath(edgeList, src, dst) {
  // implementation goes here
}

console.log(hasPath([[1, 2], [2, 3], [3, 4]], 1, 4) === true);
console.log(hasPath([[1, 2], [3, 4]], 1, 4) === false);
console.log(hasPath([[1, 2], [1, 3], [2, 4], [3, 4], [3, 5], [5, 6]], 1, 6) === true);
console.log(hasPath([], 1, 1) === true);
console.log(hasPath([[1, 2], [1, 3], [4, 5], [6, 7]], 2, 5) === false);
console.log(hasPath([[1, 2], [2, 3], [3, 4], [4, 5], [1, 5], [2, 6], [6, 7], [7, 8], [8, 5]], 1, 8) === true);
console.log(hasPath([[1, 2], [2, 3], [3, 4], [4, 5], [5, 6], [6, 3], [2, 7], [7, 8], [8, 7], [7, 9], [9, 10], [10, 11], [11, 12], [12, 10], [7, 13]], 1, 13) === true);
console.log(hasPath([[1, 2], [2, 3], [3, 1], [4, 5], [5, 6], [6, 4], [7, 8], [8, 9], [9, 10], [10, 7], [11, 12], [13, 14], [14, 15], [15, 13]], 1, 12) === false);
// All test cases should log true

Exercises

Decide on an approach for the problem and write an algorithm.

You can use DFS or BFS in this problem. The choice boils down to a personal preference. Remember that with DFS, you can opt to use a stack or recursion, while if you decide to do BFS you need to use a queue.

Share your work-in-progress with LSBot

Share what you have so far, or tell LSBot what you need help with.

Formatting Help
Preview

Edit Edit your hint request before submitting to LSBot

Share your completed work with LSBot

Have LSBot review your solution and suggest improvements.

This conversation with LSBot is temporary. Sign up for free to save your conversations with LSBot and get email notifications when LSBot reviews your solutions.

Formatting Help
Preview

Edit Edit your content before submitting to LSBot
View Our Solution
Algorithm

Let's first go through the algorithm:

Transform the edge list into an adjacency list.

Perform either a Depth-First Search or Breadth-First Search through the graph.

Maintain the destination vertex as constant and update the source vertex as you traverse the graph.

If the source vertex matches the destination vertex at any point during traversal, return true.

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.

Implement a solution.

View Our Solution

We've chose to use a DFS recursive approach:

function hasPath(edgeList, src, dst) {
  const adjList = createAdjList(edgeList);
  const visited = new Set();

  function dfs(src, dst) {
    if (src === dst) {
      return true;
    }
    visited.add(src);
    for (const neighbor of adjList.get(src)) {
      if (!visited.has(neighbor)) {
        if (dfs(neighbor, dst)) {
          return true;
        }
      }
    }
    return false;
  }
  return dfs(src, dst);
}

function createAdjList(edgeList) {
  const adjList = new Map();

  edgeList.forEach(([vertex1, vertex2]) => {
    if (!adjList.has(vertex1)) adjList.set(vertex1, []);
    adjList.get(vertex1).push(vertex2);

    if (!adjList.has(vertex2)) adjList.set(vertex2, []);
    adjList.get(vertex2).push(vertex1);
  });

  return adjList;
}

Practice: Has Path

Problem Description

Exercises

Share your work-in-progress with LSBot

Share your completed work with LSBot

View Our Solution

Algorithm

Walkthrough I

Walkthrough II

Share your work-in-progress with LSBot

Share your completed work with LSBot

View Our Solution

Ask LSBot about: Practice: Has Path

Practice: Has Path - Exercise