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

1. Introduction

Breadth-First Search (BFS) is another fundamental algorithm to traverse or search through tree or graph data structures. Unlike Depth-First Search (DFS) which ventures deep down a path before backtracking, BFS explores all the nodes at the present depth prior to moving on to nodes at the next depth level. In this guide, we will demonstrate how to implement BFS on a graph using JavaScript.

2. Program Overview

1. Instantiate the Graph class.

2. Add key methods: addVertex, addEdge, and bfs.

3. Execute our BFS on an example graph.

3. Code Program

class Graph {
    constructor() {
        this.adjacencyList = {}; // Storing vertices and their neighboring nodes
    }

    // Function to add a vertex in the graph
    addVertex(vertex) {
        if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
    }

    // Function to add an edge between two vertices
    addEdge(vertex1, vertex2) {
        this.adjacencyList[vertex1].push(vertex2);
        this.adjacencyList[vertex2].push(vertex1);
    }

    // BFS traversal using a queue
    bfs(start) {
        const queue = [start];           // Array to use as a queue for BFS traversal
        const result = [];               // List to store the BFS result
        const visited = {};              // Object to mark visited vertices
        let currentVertex;

        visited[start] = true;  // Mark the starting vertex as visited

        while(queue.length) {   // While there are still vertices in the queue
            currentVertex = queue.shift();  // Take the first vertex from the queue
            result.push(currentVertex);     // Add it to the result list

            // Visit all neighbors of the current vertex
            this.adjacencyList[currentVertex].forEach(neighbor => {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;  // Mark neighbor as visited
                    queue.push(neighbor);      // Add neighbor to the queue
                }
            });
        }

        return result;
    }
}

// Create an instance of the graph
const graph = new Graph();

// Adding vertices
graph.addVertex('A');
graph.addVertex('B');
graph.addVertex('C');
graph.addVertex('D');
graph.addVertex('E');
graph.addVertex('F');

// Connect vertices
graph.addEdge('A', 'B');
graph.addEdge('A', 'C');
graph.addEdge('B', 'D');
graph.addEdge('C', 'E');
graph.addEdge('D', 'E');
graph.addEdge('D', 'F');
graph.addEdge('E', 'F');

// Perform BFS starting from vertex A
console.log(graph.bfs('A'));

Output:

[ 'A', 'B', 'C', 'D', 'E', 'F' ]

4. Step By Step Explanation

1. Initialization: We begin our graph with an adjacency list to symbolize vertices and their associations.

2. addVertex Method: This aids in adding a vertex to the graph. A vertex is utilized as a key with its value initialized as an empty array to store its connections.

3. addEdge Method: This method associates two vertices. Both are mutually added to each other's adjacency list.

4. BFS Algorithm:

- We initiate from the designated starting vertex.

- The BFS makes use of a queue to keep track of which vertex should be visited next.

- Each time a vertex is explored, its neighbors (that haven't been visited) are queued up for a future visit.

- This ensures that vertices are visited level-by-level, exhibiting the breadth-first nature of the algorithm.

5. Example Graph: The graph has 6 vertices (A to F). The BFS begins from vertex A and covers all the neighbors of A before moving to the neighbors of B and C, and so forth.

The BFS algorithm offers insights into the structure of trees and graphs. This JavaScript implementation forms a basis for deeper delves into graph algorithms and their applications.