Breadth-First Search (BFS)

Breadth-First Search is a fundamental graph traversal algorithm used to explore a graph by visiting all its neighbor nodes at the present depth before moving on to nodes at the next depth level.

How BFS Works

1. Starting Point:

   • Begin at a starting node (usually the root in a tree or any arbitrary node in a graph).

2. Visit and Mark:

   • Visit the current node and mark it as visited to prevent revisiting.

3. Explore Neighbors:

   • Explore all unvisited neighbor nodes of the current node at the current depth level.
   • Enqueue these neighbors for further exploration in a First-In-First-Out (FIFO) order.

4. Next Depth Level:

   • Move to the next depth level and repeat steps 2 and 3 for all unvisited nodes at that level.

5. Completion:

   • Continue this process until all nodes are visited or the goal is achieved.

Key Features

• Queue: BFS uses a queue to visit nodes in the order they are discovered.
• Optimality: In unweighted graphs, BFS guarantees the shortest path.

Efficiency

• Time Complexity: O(V + E) where V is the number of vertices and E is the number of edges.
• Space Complexity: O(V) for maintaining the queue and visited nodes.

Advantages

• Guarantees shortest path in unweighted graphs.
• Good for finding the shortest path and connectivity.

Disadvantages

• Memory usage can be high, especially in large graphs.
• Not suitable for weighted graphs.

Breadth-First Search Implementation in JavaScript

Here's an example of Breadth-First Search implemented in JavaScript:

function BFS(graph, startNode) {
    const visited = new Set();
    const queue = [startNode];
    visited.add(startNode);
 
    while (queue.length > 0) {
        const currentNode = queue.shift();
        // Process the current node
        console.log(currentNode);
 
        for (const neighbor of graph[currentNode]) {
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                queue.push(neighbor);
            }
        }
    }
}
 
// Example usage
const graph = {
    A: ['B', 'C'],
    B: ['A', 'D', 'E'],
    C: ['A', 'F', 'G'],
    D: ['B'],
    E: ['B'],
    F: ['C'],
    G: ['C'],
};
 
BFS(graph, 'A'); // Starting BFS from node 'A'