JavaScript: Breadth-First Search (BFS) on a Graph

Introduction

Breadth-First Search (BFS) is a graph traversal algorithm that explores the nodes level by level. Starting from the root (or any arbitrary node), BFS visits all the nodes at the current level before moving to the next level. It uses a queue to keep track of nodes to be visited and ensures each node is visited only once.

This guide will walk you through writing a JavaScript program to perform BFS on a graph represented using an adjacency list.

Problem Statement

Create a JavaScript program that:

• Implements Breadth-First Search (BFS) on a graph.
• Traverses the graph and prints the nodes visited in BFS order.

Example:

• Input: Graph represented by an adjacency list:

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

• Starting Node: 'A'
• Output: A -> B -> C -> D -> E -> F

Solution Steps

1. Represent the Graph Using an Adjacency List: Use an object where keys represent the nodes and values represent the list of connected nodes.
2. Implement BFS:
   • Use a queue to explore nodes in a breadth-first manner.
   • Track the nodes that have already been visited to avoid revisiting.
3. Display the Traversal: Output the nodes in the order they are visited by BFS.

JavaScript Program

BFS Implementation

// JavaScript Program to Perform Breadth-First Search on a Graph
// Author: https://www.rameshfadatare.com/

// Step 1: Define the graph using an adjacency list
const graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
};

// Step 2: Define the BFS function
function bfs(startNode) {
    const visited = new Set();  // To keep track of visited nodes
    const queue = [startNode];  // Queue for BFS traversal

    console.log("Breadth-First Search Traversal:");

    // Step 3: While the queue is not empty, visit each node in breadth-first manner
    while (queue.length > 0) {
        const node = queue.shift();  // Dequeue a node from the front of the queue

        if (!visited.has(node)) {
            console.log(node);       // Print the visited node
            visited.add(node);       // Mark the node as visited

            // Step 4: Enqueue all unvisited neighbors
            for (const neighbor of graph[node]) {
                if (!visited.has(neighbor)) {
                    queue.push(neighbor);
                }
            }
        }
    }
}

// Step 5: Perform BFS starting from node 'A'
bfs('A');

Explanation

Step 1: Represent the Graph as an Adjacency List

• The graph is represented as an object where each node is a key, and its value is an array of connected nodes (its neighbors).

Step 2: Define the BFS Function

• The bfs() function starts from a given node (startNode) and explores its neighbors in breadth-first order.
• A queue is used to store nodes to visit, and a visited set is used to track nodes that have been visited.

Step 3: Dequeue a Node and Mark It as Visited

• While the queue is not empty, dequeue a node and visit it. The node is added to the visited set to avoid revisiting it in future iterations.

Step 4: Enqueue All Unvisited Neighbors

• For each node, the unvisited neighbors are added to the queue, ensuring that they are visited in the next breadth-first iteration.

Step 5: Perform BFS Starting from Node 'A'

• The BFS traversal is initiated by calling bfs('A'), and the traversal starts from node 'A'.

Output Example

Breadth-First Search Traversal:
A
B
C
D
E
F

Example with Different Input

const graph = {
    '1': ['2', '3'],
    '2': ['4'],
    '3': ['5'],
    '4': ['6'],
    '5': ['6'],
    '6': []
};

bfs('1');

Output:

Breadth-First Search Traversal:
1
2
3
4
5
6

BFS on a Disconnected Graph

In the case of a disconnected graph, you can modify the algorithm to handle unconnected components by calling BFS on all unvisited nodes.

Modified BFS for Disconnected Graph

function bfsDisconnected(graph) {
    const visited = new Set();

    for (const node in graph) {
        if (!visited.has(node)) {
            bfs(node, visited);
        }
    }
}

function bfs(node, visited) {
    const queue = [node];
    while (queue.length > 0) {
        const current = queue.shift();
        if (!visited.has(current)) {
            console.log(current);
            visited.add(current);
            for (const neighbor of graph[current]) {
                if (!visited.has(neighbor)) {
                    queue.push(neighbor);
                }
            }
        }
    }
}

// Example usage
const disconnectedGraph = {
    'A': ['B'],
    'B': [],
    'C': ['D'],
    'D': []
};
bfsDisconnected(disconnectedGraph);

Output for Disconnected Graph Example

A
B
C
D

Conclusion

This JavaScript program demonstrates how to perform Breadth-First Search (BFS) on a graph using a queue to ensure level-by-level traversal. BFS is particularly useful in shortest path problems and in cases where you need to explore nodes layer by layer. This program can be extended to handle disconnected graphs, weighted graphs, and more complex scenarios.