Breadth-First Search - Data Structures and Algorithms (DSA) Guide

Table of Contents 📚

Introduction to Breadth-First Search
BFS on Trees
BFS on Graphs
Time and Space Complexity
Conclusion

Introduction to Breadth-First Search 🌱

Breadth-First Search (BFS) is a traversal algorithm used for both trees and graphs. The algorithm starts from the root node (in a tree) or any arbitrary node (in a graph) and explores all its neighbors at the present depth before moving on to nodes at the next level of depth.

BFS on Trees 🌳

In a tree, BFS traversal would look like this:

BFS traversal order: 1, 2, 3, 4, 5

Java Implementation for BFS on Trees 🌳

import java.util.LinkedList;
import java.util.Queue;

class Node {
    int value;
    Node left, right;

    Node(int value) {
        this.value = value;
        left = right = null;
    }
}

public class BFSTree {
    Node root;

    void BFS(Node root) {
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        
        while(!queue.isEmpty()) {
            Node temp = queue.poll();
            System.out.print(temp.value + " ");
            
            if(temp.left != null) queue.add(temp.left);
            if(temp.right != null) queue.add(temp.right);
        }
    }

    public static void main(String[] args) {
        BFSTree tree = new BFSTree();
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(5);
        
        System.out.println("BFS Traversal:");
        tree.BFS(tree.root);  // Output: 1 2 3 4 5
    }
}

BFS on Graphs 🕸

In graphs, BFS can be used to traverse all reachable vertices from a given start vertex.

Graph:

1---2
|   |
4---3

BFS traversal (starting from 1): 1, 2, 4, 3

Java Implementation for BFS on Graphs 🕸

import java.util.*;

public class BFSGraph {
    private int V;
    private LinkedList<Integer> adj[];

    BFSGraph(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adj[i] = new LinkedList();
    }

    void addEdge(int v, int w) {
        adj[v].add(w);
    }

    void BFS(int start) {
        boolean visited[] = new boolean[V];
        Queue<Integer> queue = new LinkedList<>();

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

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

            for (int i : adj[current]) {
                if (!visited[i]) {
                    visited[i] = true;
                    queue.add(i);
                }
            }
        }
    }

    public static void main(String args[]) {
        BFSGraph g = new BFSGraph(4);

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

        System.out.println("BFS traversal starting from vertex 1:");

        g.BFS(1);  // Output: 1 0 2 3
    }
}

Time and Space Complexity 🕒📦

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

Conclusion 🌟

BFS is commonly used for traversing trees and graphs, shortest path finding, network topology discovery, and many more applications. Understanding the BFS algorithm and its implementations in various scenarios will definitely give you an edge in problem-solving.

If you find this guide useful, please share with others, and spread the knowledge!