NUHMAN.com

Breadth-First Search (BFS) is a popular graph traversal algorithm used in a wide variety of applications, including network broadcasting, shortest path problems, and recommendation systems. In Java, implementing BFS is straightforward using a queue and a set to track visited nodes.

In this article, we'll demonstrate how to implement BFS on a graph represented using an adjacency list.

1. Recap: Graph Implementation with Adjacency List

Before we dive into BFS, let’s recall our graph structure using a Map<Vertex, List<Vertex>>.

Vertex Class

java

import java.util.Objects;

public class Vertex {
    private String label;

    public Vertex(String label) {
        this.label = label;
    }

    public String getLabel() {
        return label;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Vertex)) return false;
        Vertex vertex = (Vertex) o;
        return Objects.equals(label, vertex.label);
    }

    @Override
    public int hashCode() {
        return Objects.hash(label);
    }

    @Override
    public String toString() {
        return label;
    }
}

2. BFS Implementation in the Graph Class

We'll now add a bfs() method to our Graph class.

java

import java.util.*;

public class Graph {
    private final Map<Vertex, List<Vertex>> adjVertices;

    public Graph() {
        this.adjVertices = new HashMap<>();
    }

    public void addVertex(String label) {
        adjVertices.putIfAbsent(new Vertex(label), new ArrayList<>());
    }

    public void removeVertex(String label) {
        Vertex v = new Vertex(label);
        adjVertices.values().forEach(e -> e.remove(v));
        adjVertices.remove(v);
    }

    public void addEdge(String label1, String label2) {
        Vertex v1 = new Vertex(label1);
        Vertex v2 = new Vertex(label2);
        adjVertices.get(v1).add(v2);
        adjVertices.get(v2).add(v1); // For undirected graph
    }

    public void removeEdge(String label1, String label2) {
        Vertex v1 = new Vertex(label1);
        Vertex v2 = new Vertex(label2);
        List<Vertex> eV1 = adjVertices.get(v1);
        List<Vertex> eV2 = adjVertices.get(v2);
        if (eV1 != null) eV1.remove(v2);
        if (eV2 != null) eV2.remove(v1);
    }

    public List<Vertex> getAdjVertices(String label) {
        return adjVertices.get(new Vertex(label));
    }

    public void printGraph() {
        for (Vertex v : adjVertices.keySet()) {
            System.out.print(v + " -> ");
            for (Vertex w : adjVertices.get(v)) {
                System.out.print(w + " ");
            }
            System.out.println();
        }
    }

    // === Breadth-First Search ===
    public void bfs(String startLabel) {
        Vertex startVertex = new Vertex(startLabel);
        if (!adjVertices.containsKey(startVertex)) {
            System.out.println("Vertex not found in the graph.");
            return;
        }

        Set<Vertex> visited = new HashSet<>();
        Queue<Vertex> queue = new LinkedList<>();

        visited.add(startVertex);
        queue.add(startVertex);

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

            for (Vertex neighbor : adjVertices.get(current)) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.add(neighbor);
                }
            }
        }

        System.out.println();
    }
}

3. Example Usage of BFS

Let’s see BFS in action:

java

public class Main {
    public static void main(String[] args) {
        Graph graph = new Graph();
        graph.addVertex("A");
        graph.addVertex("B");
        graph.addVertex("C");
        graph.addVertex("D");
        graph.addVertex("E");

        graph.addEdge("A", "B");
        graph.addEdge("A", "C");
        graph.addEdge("B", "D");
        graph.addEdge("C", "D");
        graph.addEdge("D", "E");

        graph.printGraph();

        System.out.println("BFS starting from vertex A:");
        graph.bfs("A");
    }
}

Output

mathematica

A -> B C 
B -> A D 
C -> A D 
D -> B C E 
E -> D 
BFS starting from vertex A:
A B C D E 

4. How BFS Works

ConceptDescriptionQueueA Queue is used to explore vertices in FIFO order.Visited SetEnsures each vertex is visited only once, preventing cycles and duplicates.TraversalStarts at the root node, explores neighbors first, then deeper nodes.

BFS is ideal for finding the shortest path (in terms of edges) in unweighted graphs and exploring all nodes reachable from a given source.

5. Real-World Applications of BFS

• Shortest Path in Unweighted Graphs
• Friend Suggestions in Social Networks
• Web Crawlers
• Broadcast Networks
• AI/Game Trees

Final Thoughts

BFS is a foundational algorithm in graph theory and is useful across many domains. With a simple implementation using Java collections like Queue and Set, it's easy to integrate BFS into your projects for graph traversal and analysis.