Breadth First Search (BFS) is a graph traversal algorithm that visits nodes level by level using a queue (FIFO). It is commonly used to find the shortest path in an unweighted graph.

Key Points (Quick Revision)

• BFS uses a Queue (FIFO)
• It visits nodes level by level
• It guarantees the shortest path (unweighted graph)
• Time Complexity: O(V + E)
• Space Complexity: O(V)

BFS in Very Simple Words

BFS is like spreading out step by step.

• Start from one node
• Visit all nearby nodes first
• Then go to the next level

It works like a wave or circle expansion.

Real-Life Example

Think of:

• Spreading news in a group
• Water waves after dropping a stone
• Fire spreading in a forest

First nearby → then next → then next. This is exactly how BFS works.

Example Graph

    0
   / \
  1   2
 / \
3   4

BFS Output:

0 → 1 → 2 → 3 → 4

How BFS Works (Step-by-Step)

1. Start from a node
2. Add it to the queue
3. Mark it as visited
4. Remove from queue
5. Visit all neighbors
6. Add unvisited neighbors to the queue
7. Repeat

Algorithm (Simple Version)

Start node
→ Add to queue
→ While queue is not empty:
   - Remove node
   - Print node
   - Add all unvisited neighbors

Java Code – BFS using Adjacency List

import java.util.*;

public class BFSGraph {

    int vertices;
    LinkedList<Integer>[] list;

    public BFSGraph(int v) {
        vertices = v;
        list = new LinkedList[v];

        for (int i = 0; i < v; i++) {
            list[i] = new LinkedList<>();
        }
    }

    public void addEdge(int source, int destination) {
        list[source].add(destination);
        list[destination].add(source); // undirected
    }

    public void bfs(int start) {

        boolean[] visited = new boolean[vertices];
        Queue<Integer> queue = new LinkedList<>();

        visited[start] = true;
        queue.add(start);

        while (!queue.isEmpty()) {

            int node = queue.poll();
            System.out.print(node + " ");

            for (int neighbor : list[node]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.add(neighbor);
                }
            }
        }
    }

    public static void main(String[] args) {

        BFSGraph g = new BFSGraph(5);

        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 3);
        g.addEdge(1, 4);

        System.out.print("BFS Traversal: ");
        g.bfs(0);
    }
}

When to Use BFS

Use BFS when:

• You need the shortest path (unweighted graph)
• You want level-by-level traversal
• You are solving minimum steps problems
• You are working with networks or connections

Applications of BFS

• Shortest path (unweighted graph)
• Social network connections
• Web crawling
• GPS systems
• Network broadcasting

BFS vs DFS (Simple Difference)

FAQ – Direct Questions & Answers

What is BFS in Data Structures?

BFS is a graph traversal algorithm that visits nodes level by level using a queue.

Which data structure is used in BFS?

A queue (FIFO) is used in BFS.

What is BFS used for?

BFS is used for shortest path, graph traversal, and network problems.

What is the time complexity of BFS?

Time Complexity of BFS is O(V + E).