# 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.

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
}

// Function to add an edge between two vertices
}

// 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
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();

// Connect vertices

// 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.