Has Path

Question

Given a graph and a destination node on the graph return true, if there's a path from the source node to the destination node.

input:

source: 1

Destination: 4

Output:

TRUE

Solution

We can solve this either using depth-first search or using breadth-first search. For our solution here we will use depth-first search.

When looking at the time complexity of the algorithm we can say that n would be the number of nodes and e the number of edges. Thus we can state in the worse case our time complexity would be O(n+e), and our space complexity would be O(n).

Javascript

const depthFirstSearch = (graph, source, destination) => {
  if (source === destination) {
    return true;
  }
  for (const neighbor of graph[source]) {
    if (depthFirstSearch(graph, neighbor, destination) === true) {
      return true;
    }
  }
  return false;
};

Java

Concepts

• Graphs
• Traverse

Patterns

• DFS