Breadth First Search or BFS for a Graph

bysantosh •سبتمبر 06, 2021

0

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: Breadth-First Search (BFS)

To solve this problem, we use a Breadth-First Search (BFS) algorithm. BFS is particularly suitable for finding the shortest path in an unweighted graph and checking for connectivity between nodes.

Understanding BFS

Breadth-First 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

Step-by-Step 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'.
Processing 'g':
- Dequeue 'g'. Check if it is 'k'. It isn’t.
- Enqueue its neighbor 'h'.
Processing 'i':
- Dequeue 'i'. Check if it is 'k'. It isn’t.
- Enqueue its neighbors 'g' and 'k'.
Processing 'h':
- Dequeue 'h'. Check if it is 'k'. It isn’t.
- 'h' has no neighbors, so nothing to enqueue.
Processing 'g' Again:
- Dequeue 'g' (it was already processed). Nothing new to explore.
Processing 'k':
- Dequeue 'k'. This matches our destination node, so we return true.

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 BFS-based 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 graph-related interview questions.