Java Breadth-First Search (BFS) Tutorial

Welcome to the Java Breadth-First Search (BFS) tutorial! In this lesson, we'll explore the BFS algorithm, a common strategy used in graph traversal. We'll cover its implementation, real-world applications, and see it in action with practical examples. Let's get started!

What is Breadth-First Search (BFS)?

💡 BFS is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node in the case of graphs) and explores all of the neighbor nodes at the present depth prior to moving on to nodes at the next depth level.

Why use BFS?

✅ BFS is useful in many scenarios, such as finding the shortest path between nodes in an unweighted graph, checking if a graph is connected, or determining the number of connected components in a graph.

BFS vs. Depth-First Search (DFS)

BFS and Depth-First Search (DFS) are two common graph traversal algorithms. While both algorithms visit all vertices of a connected graph, they differ in their traversal order and use cases.

BFS traverses breadth-wise, exploring all nodes at the current depth before moving to the next. It's useful for finding the shortest path in an unweighted graph and determining the number of connected components.
DFS traverses depth-wise, exploring as far as possible along each branch before backtracking. It's useful for detecting cycles in a graph, topological sorting, and solving graph coloring problems.

BFS Data Structures

To implement BFS, we'll need a data structure to represent the graph and a queue to keep track of nodes to be visited. A common choice for the graph representation is an adjacency list.

BFS Pseudocode

Here's a high-level overview of the BFS algorithm:

Initialize an empty queue q and a boolean array visited to keep track of visited nodes.
Add the starting node to the queue and mark it as visited.
While the queue is not empty, perform the following steps:
1. Dequeue a node u from the queue.
2. For each neighbor v of u that has not been visited:
  1. Mark v as visited.
  2. Add v to the queue.
The algorithm terminates when all nodes have been visited and the queue is empty.

Implementing BFS in Java

Now, let's see how to implement BFS in Java using the adjacency list representation.

java

import java.util.*;

public class BreadthFirstSearch {
    private static final String UNVISITED = "Unvisited";
    private static final String VISITED = "Visited";

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

        System.out.println("BFS of graph:");
        bfs(graph, 0);
    }

    private static void bfs(Graph graph, int source) {
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[graph.getVertexCount()];

        // Initialize the source node and mark it as visited
        queue.add(source);
        visited[source] = true;

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

            // Visit and enqueue neighbors
            for (int neighbor : graph.getAdjacencies(current)) {
                if (!visited[neighbor]) {
                    queue.add(neighbor);
                    visited[neighbor] = true;
                }
            }
        }
    }
}

class Graph {
    private final int[] adjacencies;
    private final int vertexCount;

    public Graph(int vertexCount) {
        this.vertexCount = vertexCount;
        this.adjacencies = new int[vertexCount];
        for (int i = 0; i < vertexCount; i++) {
            adjacencies[i] = -1;
        }
    }

    public void addEdge(int vertex1, int vertex2) {
        adjacencies[vertex1] = vertex2;
    }

    public int[] getAdjacencies(int vertex) {
        return adjacencies[vertex] >= 0 ? new int[]{adjacencies[vertex]} : new int[0];
    }

    public int getVertexCount() {
        return vertexCount;
    }
}

📝 Note: This example demonstrates an unweighted undirected graph with adjacency list representation. You can extend this code to handle weighted graphs and directed graphs if needed.

BFS in Action

With the BFS implementation ready, let's observe the BFS traversal of the sample graph from the main function:

BFS of graph:
0 1 2 3 4 5

This output shows the BFS traversal of the given graph, starting from vertex 0.

Java Breadth-First Search (BFS) Tutorial

Java Breadth-First Search (BFS) Tutorial

What is Breadth-First Search (BFS)?

Why use BFS?

BFS vs. Depth-First Search (DFS)

BFS Data Structures

BFS Pseudocode

Implementing BFS in Java

BFS in Action

Quiz