Breadth-First Search (BFS) is a graph traversal algorithm that explores the graph level by level, visiting all nodes at the present depth level before moving on to nodes at the next depth level. BFS is widely used in various applications such as finding the shortest path in unweighted graphs, solving puzzles, and many other graph-based problems.

In this blog, we’ll explore the BFS algorithm, its properties, and provide Java code examples for BFS in both graphs and trees.

📚 What is Breadth-First Search (BFS)?

Breadth-First Search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the root node (or any arbitrary node in the case of a graph) and explores the neighbor nodes at the present depth level before moving on to nodes at the next depth level. BFS uses a queue to explore the nodes, ensuring that nodes are processed in the order they are discovered.

BFS Algorithm Steps:

  1. Start at the root node (or any arbitrary node in the graph).
  2. Mark the node as visited and enqueue it.
  3. While the queue is not empty:
    • Dequeue a node.
    • Visit all its unvisited neighbors, mark them as visited, and enqueue them.
  4. Repeat the process until all reachable nodes are visited.

BFS is particularly useful when you want to explore all neighbors of a node before moving deeper into the graph or tree.

🛠️ Types of BFS

BFS can be used in several applications:

  • Finding the Shortest Path: BFS can find the shortest path in an unweighted graph (where all edges have the same weight).
  • Level-Order Traversal (in Trees): BFS is used in level-order traversal of binary trees.
  • Finding Connected Components: BFS can be used to find all nodes in the same connected component of a graph.
  • Cycle Detection: BFS can also be used for detecting cycles in undirected graphs.
  • Social Networks: BFS can model the spread of information or viral content through social networks.

🧑‍💻 BFS in Java

1. BFS for Graphs (Using Queue)

In BFS, we use a queue to explore the nodes level by level. We start from the source node, mark it as visited, and then explore its neighbors by adding them to the queue. Nodes are processed in the order they are dequeued.

BFS for Graphs (Using Queue) 

import java.util.*;

class Graph {
    private Map<Integer, List<Integer>> adjList;

    public Graph() {
        adjList = new HashMap<>();
    }

    public void addEdge(int u, int v) {
        adjList.putIfAbsent(u, new ArrayList<>());
        adjList.putIfAbsent(v, new ArrayList<>());
        adjList.get(u).add(v);
        adjList.get(v).add(u); // For an undirected graph
    }

    public void bfs(int start) {
        Set<Integer> visited = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        visited.add(start);

        while (!queue.isEmpty()) {
            int node = queue.poll();
            System.out.print(node + " ");

            // Explore all unvisited neighbors
            for (int neighbor : adjList.get(node)) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.add(neighbor);
                }
            }
        }
    }
}

public class BFSExample {
    public static void main(String[] args) {
        Graph graph = new Graph();
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 3);
        graph.addEdge(1, 4);

        System.out.println("BFS starting from node 0:");
        graph.bfs(0);  // Starting BFS from node 0
    }
}

Explanation:

  • We create an adjacency list to represent the graph.
  • We use a queue to hold the nodes to be explored.
  • We visit a node, explore its neighbors, and add unvisited neighbors to the queue for future exploration.
  • A set visited ensures we don’t revisit nodes.

Output: 

BFS starting from node 0:
0 1 2 3 4

2. BFS for Trees (Level-Order Traversal)

In binary trees, BFS is often referred to as level-order traversal, where we explore all the nodes at a given depth level before moving to the next level.

BFS for Binary Tree (Level-Order Traversal) 

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;

    public TreeNode(int val) {
        this.val = val;
        this.left = this.right = null;
    }
}

class BinaryTree {
    TreeNode root;

    public void bfs() {
        if (root == null) return;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            System.out.print(node.val + " ");

            // Add left and right children to the queue
            if (node.left != null) queue.add(node.left);
            if (node.right != null) queue.add(node.right);
        }
    }
}

public class BFSBinaryTreeExample {
    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();
        tree.root = new TreeNode(1);
        tree.root.left = new TreeNode(2);
        tree.root.right = new TreeNode(3);
        tree.root.left.left = new TreeNode(4);
        tree.root.left.right = new TreeNode(5);
        tree.root.right.left = new TreeNode(6);

        System.out.println("Level-Order Traversal (BFS) of the Binary Tree:");
        tree.bfs();  // Starting BFS on the tree
    }
}

Explanation:

  • We use a queue to hold the nodes of the tree.
  • We start from the root and explore each level, adding the child nodes to the queue for the next level.
  • This continues until all levels are visited.

Output: 

Level-Order Traversal (BFS) of the Binary Tree:
1 2 3 4 5 6

🧠 Time and Space Complexity

Time Complexity:

  • BFS takes O(V + E) time, where V is the number of vertices (nodes) and E is the number of edges in the graph.
  • For binary trees, it takes O(n), where n is the number of nodes in the tree, as we visit each node exactly once.

Space Complexity:

  • BFS has O(V) space complexity, where V is the number of nodes in the graph (or tree). This is because we store nodes in a queue during the exploration.
  • In trees, the space complexity is also O(n), where n is the number of nodes, as the queue may store all the nodes at the current level.

🎯 Applications of BFS

  1. Shortest Path in Unweighted Graphs: BFS is ideal for finding the shortest path in unweighted graphs (e.g., the fewest number of edges between two nodes).
  2. Level-Order Traversal (Trees): BFS is used to perform level-order traversal in trees.
  3. Connected Components: BFS can help find all nodes in a connected component of an undirected graph.
  4. Cycle Detection: In undirected graphs, BFS can detect cycles by checking if a node is visited twice during traversal.
  5. Social Networks: BFS can be used to model how information spreads in social networks, such as finding the shortest chain between two people.

📝 Interview Tips

  • Graph Representation: Ensure you understand how to represent a graph using adjacency lists or matrices. Be ready to convert between these representations.
  • Edge Cases: Handle edge cases like disconnected graphs, graphs with a single node, or cyclic graphs.
  • Shortest Path Problems: BFS is commonly used to solve shortest path problems in unweighted graphs, so be prepared for problems like "find the shortest path between two nodes."
  • Tree Traversal: BFS is useful for level-order traversal in trees. Understand how BFS can be adapted to work with binary trees.
  • Space Complexity Considerations: BFS uses a queue, so be mindful of space complexity when dealing with large graphs or trees.

📝 Conclusion

Breadth-First Search (BFS) is a powerful algorithm for graph traversal that ensures nodes are explored level by level. It is commonly used for finding the shortest path in unweighted graphs, traversing binary trees, and solving many other graph-related problems. Whether you are exploring social networks, solving puzzles, or searching for connected components, BFS is a fundamental algorithm that should be in your toolkit.