Breadth First Search in JavaScript

Introduction

Graphs are a fundamental data structure in computer science used to model pairwise relations between objects. They consist of vertices (nodes) which are connected by edges. Many real-world problems can be represented using graphs, such as analyzing networks, finding paths, and studying relationships between entities.

To efficiently search or traverse through a graph to find a target node or the shortest path, we need graph search algorithms. A foundational graph traversal technique is known as breadth first search (BFS). In this article, we‘ll take an in-depth look at breadth first search, understand how it works, and implement it in JavaScript with code examples.

What is Breadth First Search?

Breadth first search is a graph traversal algorithm that explores all neighboring vertices at the current level before moving on to vertices at the next level. It starts at a source node and visits all its adjacent nodes, then proceeds to visit all the unexplored neighbors of those nodes, and so on, until the entire connected component of the source node is visited.

BFS explores the graph in a breadthward motion, expanding the frontier between discovered and undiscovered nodes uniformly across the breadth of the frontier. It uses a queue data structure to keep track of the nodes to visit next.

The key distinguishing factor of BFS is that it visits all nodes at the current level before progressing to the next level. In contrast, depth first search (DFS) explores as far as possible along each branch before backtracking.

Some characteristics of BFS:

• Explores the graph level by level, visiting all nodes at the current level before moving to the next
• Uses a queue to keep track of nodes to visit next
• Finds the shortest path between the source node and all other reachable nodes
• Time complexity of O(V + E) where V is vertices and E is edges
• Space complexity of O(V) to store the queue

BFS is well-suited for problems that involve finding the shortest path or distance from a source node. It can also be used to test if a graph is bipartite, to find connected components, or to detect cycles. However, BFS may not be ideal if the graph is very wide, as it could consume a lot of memory to store the queue.

The BFS Algorithm

Now that we understand how BFS works at a high level, let‘s walk through the steps of the BFS algorithm:

1. Start at the source node s and add it to an empty queue Q
2. Mark s as visited and set its distance as 0
3. While Q is not empty, repeat steps 4-7
4. Remove the first node u from Q
5. For each unvisited neighbor v of u:
   • Mark v as visited
   • Set v‘s distance as u‘s distance + 1
   • Add v to the end of Q
6. If the target node is found, exit
7. Else, continue to the next node in Q

In essence, BFS uses a queue to keep track of which node to visit next. It starts with the source node, marks it as visited, and adds it to the queue. Then it processes nodes from the queue one by one, marking their unvisited neighbors as visited, setting their distance, and adding them to the queue. This continues until the queue is empty or the target node is found.

Here‘s the pseudocode for the BFS algorithm:

function BFS(graph, source):
    Q = new Queue()
    visited = new Set()
    distance = new Map()

    Q.enqueue(source)
    visited.add(source)
    distance[source] = 0

    while Q is not empty:
        u = Q.dequeue()
        for each neighbor v of u:
            if v is not in visited:
                visited.add(v)
                distance[v] = distance[u] + 1
                Q.enqueue(v)

Implementing BFS in JavaScript

To implement BFS in JavaScript, we first need a way to represent our graph. We‘ll use an adjacency list, where each vertex is a key in a dictionary, and the corresponding value is an array containing its neighboring nodes.

Here‘s an example of representing an undirected graph in JavaScript:

const graph = {
  ‘A‘: [‘B‘, ‘C‘],
  ‘B‘: [‘A‘, ‘D‘, ‘E‘],
  ‘C‘: [‘A‘, ‘F‘],
  ‘D‘: [‘B‘],
  ‘E‘: [‘B‘, ‘F‘],
  ‘F‘: [‘C‘, ‘E‘]
};

Next, we‘ll implement the BFS algorithm based on the pseudocode we discussed earlier. We‘ll use a JavaScript Map to keep track of the distances and a Set to track visited nodes.

function bfs(graph, source) {
  const queue = [source];
  const visited = new Set();
  const distances = new Map();

  visited.add(source);
  distances.set(source, 0);

  while (queue.length > 0) {
    const vertex = queue.shift();

    for (const neighbor of graph[vertex]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        distances.set(neighbor, distances.get(vertex) + 1);
        queue.push(neighbor);
      }
    }
  }

  return distances;
}

Our bfs function takes the graph adjacency list and the source vertex as input. It initializes a queue with the source vertex, marks it as visited, and sets its distance as 0.

Then it enters a loop that continues as long as there are vertices in the queue. It removes the first vertex u from the queue and iterates through its unvisited neighbors. For each unvisited neighbor v, it marks v as visited, sets its distance as u‘s distance + 1, and adds it to the end of the queue.

Finally, once the queue is empty, the function returns a Map containing the distances of all nodes reachable from the source.

Let‘s test our BFS implementation on the example graph:

console.log(bfs(graph, ‘A‘));

Output:

Map(6) {
  ‘A‘ => 0,
  ‘B‘ => 1,
  ‘C‘ => 1,
  ‘D‘ => 2, 
  ‘E‘ => 2,
  ‘F‘ => 2
}

The output shows the distances of all nodes from the source node ‘A‘. Nodes ‘B‘ and ‘C‘ have a distance of 1 since they are direct neighbors of ‘A‘. Nodes ‘D‘, ‘E‘, and ‘F‘ have a distance of 2 as they are neighbors of the neighbors of ‘A‘.

Complexity Analysis

Let‘s analyze the time and space complexity of the BFS algorithm:

• Time Complexity: In the worst case, BFS visits every vertex and edge in the graph once. The time complexity is O(V + E), where V is the number of vertices and E is the number of edges. This is because we process each vertex once, and for each vertex, we iterate through its adjacency list, which in total sums up to the number of edges E.

• Space Complexity: BFS uses a queue to store vertices to visit next and a set/map to keep track of visited vertices and distances. In the worst case, the queue could contain all vertices, so the space complexity is O(V) to store the queue. The space for the visited set and distance map is also O(V). Therefore, the overall space complexity of BFS is O(V).

Some optimizations to improve the efficiency of BFS include:

• Using an adjacency list instead of an adjacency matrix to represent the graph, as it‘s more space-efficient for sparse graphs
• Terminating the search early if the target node is found
• Using a priority queue instead of a regular queue to find the shortest path faster

Applications of BFS

Breadth first search has various applications in solving graph-related problems. Some common use cases include:

1. Finding the shortest path or minimum distance between two nodes in an unweighted graph. For example, finding the fewest number of hops between two users in a social network.

2. Testing if a graph is bipartite (i.e., can be divided into two independent sets such that no two vertices within the same set are adjacent). BFS can be used to assign colors to vertices and check if any adjacent vertices have the same color.

3. Finding connected components in an undirected graph. BFS can traverse the graph and group nodes into connected components based on reachability.

4. Detecting cycles in a graph. By keeping track of the parent of each visited node, BFS can identify if there is a cycle when it encounters an already visited node that is not the parent of the current node.

5. Solving puzzle or maze problems where the goal is to find the minimum number of moves to reach the target state. BFS can explore all possible states level by level until it finds the target.

6. Web crawling and indexing web pages. BFS can systematically visit all pages reachable from a starting URL and index their contents for search engines.

These are just a few examples, but BFS is a versatile algorithm that can be adapted to solve many graph traversal and shortest path problems efficiently.

Conclusion

In this article, we explored breadth first search, a fundamental graph traversal algorithm. We learned how BFS works by visiting nodes level by level, utilizing a queue to keep track of nodes to visit next. We implemented BFS in JavaScript and analyzed its time and space complexity.

BFS is an essential tool in a programmer‘s algorithmic toolkit, as it can efficiently solve many graph-related problems such as finding shortest paths, connected components, and testing graph properties. By understanding how BFS works and practicing its implementation, you‘ll be well-equipped to tackle graph traversal and shortest path problems in your own projects.

To further solidify your understanding of BFS, I encourage you to practice implementing it on various graph problems. Try visualizing the step-by-step process of BFS on different graph examples to develop your intuition. Experiment with optimizations and variations of BFS, such as using a priority queue or adapting it for specific problem constraints.

Remember, mastering graph algorithms like BFS takes practice and experience. Don‘t get discouraged if it feels challenging at first – with time and effort, you‘ll develop the skills to confidently apply BFS and other graph algorithms in your problem-solving arsenal.

Happy coding, and may your graph traversals be breadth-first and efficient!

Additional Resources

If you‘d like to learn more about breadth first search and related topics, here are some excellent resources:

• Breadth First Search (BFS) | Coursera
• Breadth First Search or BFS for a Graph – GeeksforGeeks
• Graph Traversals – BFS & DFS -Breadth First Search and Depth First Search (YouTube)
• Breaking Down Breadth-First Search | basecs – Medium