Graph traversal algorithms are essential tools in computer science for navigating through data structures that represent networks, relationships, or connections between entities. One classic problem in graph theory is determining whether there exists a path between two nodes (or vertices) in a directed graph. This problem is a foundational topic for both beginners and advanced programmers.
Problem Statement
Given a directed graph and two nodes (a source and a destination), determine if there is a path from the source node to the destination node. This can be visualized as trying to find a route between two points in a network.
For example, consider the graph below:
const graph = {
f: ['g', 'i'],
g: ['h'],
h: [],
i: ['g', 'k'],
j: ['i'],
k: []
};
We want to determine if there is a path from node 'f'
to node 'k'
. In this example, the answer is true
.
Approach: BreadthFirst Search (BFS)
To solve this problem, we use a BreadthFirst Search (BFS) algorithm. BFS is particularly suitable for finding the shortest path in an unweighted graph and checking for connectivity between nodes.
Understanding BFS
BreadthFirst Search (BFS) explores all nodes at the present depth level before moving on to the nodes at the next depth level. The BFS algorithm works by using a queue to keep track of the nodes to be explored. This ensures that nodes are processed in the order they were discovered.
Here’s the BFS approach for finding a path in a graph:
 Initialize a Queue: Start with the source node and add it to a queue.
 Process the Queue: While the queue is not empty:
 Dequeue a node.
 If the dequeued node is the destination, return
true
.  Otherwise, enqueue all its unvisited neighbors.
 No Path Found: If the queue becomes empty without finding the destination, return
false
.
Code Implementation
Let’s dive into the code:
const hasPath = (graph, src, dst) => {
return helper(graph, src, dst);
};
const helper = (graph, src, dst) => {
const queue = [src]; // Initialize the queue with the source node
while (queue.length > 0) { // Continue until the queue is empty
const current = queue.shift(); // Dequeue the first node
if (current === dst) { // If we have reached the destination node
return true;
}
for (let nb of graph[current]) { // Enqueue all unvisited neighbors
queue.push(nb);
}
}
return false; // If we exhaust the queue without finding the destination
};
// Example Usage
const graph = {
f: ['g', 'i'],
g: ['h'],
h: [],
i: ['g', 'k'],
j: ['i'],
k: []
};
console.log(hasPath(graph, 'f', 'k')); // Output: true
StepbyStep Breakdown
To understand the flow of the hasPath
function, let’s go through an example of how it works for hasPath(graph, 'f', 'k')
:

Initialization: Start with a queue initialized with the source node
'f'
. 
Processing
'f'
: Dequeue
'f'
. Check if it is the destination'k'
. It isn’t.  Enqueue its neighbors
'g'
and'i'
.
 Dequeue

Processing
'g'
: Dequeue
'g'
. Check if it is'k'
. It isn’t.  Enqueue its neighbor
'h'
.
 Dequeue

Processing
'i'
: Dequeue
'i'
. Check if it is'k'
. It isn’t.  Enqueue its neighbors
'g'
and'k'
.
 Dequeue

Processing
'h'
: Dequeue
'h'
. Check if it is'k'
. It isn’t. 'h'
has no neighbors, so nothing to enqueue.
 Dequeue

Processing
'g'
Again: Dequeue
'g'
(it was already processed). Nothing new to explore.
 Dequeue

Processing
'k'
: Dequeue
'k'
. This matches our destination node, so we returntrue
.
 Dequeue
Advanced Considerations

Time Complexity:
The time complexity of BFS is O(V + E), where V is the number of vertices and E is the number of edges. This is because each vertex and edge is processed once. 
Space Complexity:
The space complexity is O(V) due to the storage requirements of the queue and the set to keep track of visited nodes.
Conclusion
The BFSbased approach to finding a path between two nodes in a directed graph is straightforward yet powerful. It guarantees the shortest path in an unweighted graph and is the foundation for more advanced algorithms like Dijkstra’s and A* search.
By understanding the basics of BFS and practicing problems like this, you’ll gain a deeper insight into graph traversal algorithms and be better prepared to tackle complex graphrelated interview questions.
Further Reading
Happy coding!