Write a function that determines if a path exists between two vertices of a directed graph.
Recall that a graph is a collection of connections, or 'edges', linking together nodes or verticies. In a directed graph, each edge is like an arrow or a one-way street-- an edge linking A to B indicates that A connects to B, but not that B connects to A.
The graph passed to the function will be represented as an object with a structure sometimes called an 'adjacency list' or 'adjacency map', in which each key represents a node in the graph, and each value will consist in an array of nodes which can be reached from the key. For example, the following object:
{
a: ['b'],
b: ['c', 'd'],
c: ['d'],
d: []
}represents the graph:
The doesPathExist function we'll be writing will be passed an adjacency map as well as two strings indicating the starting node and ending node. The function will return a boolean indicating if a path exists from the starting to the ending node:
function doesPathExist(graph, start, end) {
// your code here
}
doesPathExist(graph, 'a', 'b') // true
doesPathExist(graph, 'b', 'a') // false
doesPathExist(graph, 'a', 'd') // true
doesPathExist(graph, 'a', 'a') // falseHere are some examples for another graph. Notice that this graph contains a node that points to itself and also a 'cycle' (that is, a loop involving multiple nodes):
const graph = {
a: ['a', 'c'],
c: ['r', 's'],
r: ['a'],
s: []
}
doesPathExist(graph, 'a', 'a') // true
doesPathExist(graph, 'c', 'c') // true
doesPathExist(graph, 'r', 's') // true
doesPathExist(graph, 's', 'a') // falseMake it clear that the nodes in this graph are represented by strings like 'a' and 'b', not by instances of a Node class, in contrast to some of the problems we worked with earlier in the week.
Be sure the interviewee understands what it means to say that a graph is directed. Having them construct their own example graph and adjacency map will help them concretize their understanding and will help you to assess it.
Your interviewee may also not realize that we are allowing cyclic connections in these graphs. It will be easy to see if they understand this if they have picked an example showing a cyclic structure; if they haven't chosen a cyclic graph, it might be useful to borrow the marker to add an edge or two until the graph is cyclic.
This problem is essentially a DFS/BFS problem. Either algorithm is sufficient, and there are both recursive and iterative solutions. The only catch is that graphs can be cyclic. In other words, it's possible for a loop to exist in the graph.
It might be useful to suggest that the interviewee come up with a solution that does not account for cycles which they can then refine.
See if they can come up with their own way of keeping track of visited nodes. If they are stuck, you can suggest that they use a separate object or array, either 'globally' or as another argument to the function (or helper function, as the case may be).
It's possible to write a very terse solution using Array.prototype.some(). Consider suggesting this to your interviewee.
Be sure your interviewee tests their implementation on both acyclic and cyclic graphs.
If they finish early, ask them to think about time and space complexity.
Can they think of alternative data structures for keeping track of visited nodes? A set can be a good choice, here.
const doesPathExist = (graph, start, target, visited = {}) => {
if (!graph[start]) return false
visited[start] = true;
return graph[start].some((vertex) => {
if (vertex === target) return true;
if (!visited[vertex]) {
return doesPathExist(graph, vertex, target, visited);
} else {
return false;
}
});
}Note that we're using an object to keep track of visted notes. Note also the way in which we initialize an additional argument to allow us to pass this object to the recursive function invocation-- this is a useful trick that lets us not pollute global scope while avoiding the need for a helper function.
const doesPathExist = (graph, start, target) => {
if (!graph[start]) return false;
const queue = [start];
const visited = {};
while (queue.length) {
const current = queue.shift();
visited[current] = true;
// can't use `.forEach` because we need to `return`
for (let i = 0; i < graph[current].length; i += 1) {
const child = graph[current][i];
// have to do this check here to properly handle nodes pointing to themselves
if (child === target) return true;
if (!visited[child]) {
queue.push(child);
}
}
}
return false;
};Both DFS and BFS take O(V + E) time where V is the number of vertices or nodes and E is the number of edges. We MUST attempt to visit every node, which will take us through potentially many edges.
For acyclic graphs, we might visit every node and hit the leaves. For cyclic graphs, the cycle might not occur until a 'leaf'. For dense graphs, edges will dominate. For sparse graphs, vertices will dominate
Keeping track of a 'visited' object means we need O(V) additional space.
All trees are graphs. Techniques you learn to solve graphs can be applied for various kinds of trees, and often vice versa. You will often run into problems where you need to track 'visited' nodes. Sometimes this means keeping a hash table of visited nodes; if nodes are objects it might mean adding a 'visted' property.