Understanding Graph Traversal: Implementing BFS in Java

Graph traversal is a fundamental concept in computer science, essential for various applications like network routing, social network analysis, and game development. In this blog post, we’ll explore the Breadth-First Search (BFS) traversal algorithm. We’ll implement BFS in Java and break down the code to make it easy to understand for absolute beginners.

Graph Representation

Before diving into the BFS algorithm, let’s first understand how to represent a graph in Java. We’ll use an adjacency list to represent the graph.

Here’s the Graph class:

import java.util.*;

// Graph class using adjacency list representation
public class Graph {
    private int vertices; // Number of vertices
    private LinkedList<Integer>[] adjList; // Adjacency list

    // Constructor
    public Graph(int vertices) {
        this.vertices = vertices;
        adjList = new LinkedList[vertices];
        for (int i = 0; i < vertices; i++) {
            adjList[i] = new LinkedList<>();
        }
    }

    // Add edge to the graph
    public void addEdge(int src, int dest) {
        adjList[src].add(dest); // Add edge from src to dest
        adjList[dest].add(src); // Add edge from dest to src (for undirected graph)
    }

    // Print the adjacency list of the graph
    public void printGraph() {
        for (int i = 0; i < vertices; i++) {
            System.out.print("Vertex " + i + ": ");
            for (Integer vertex : adjList[i]) {
                System.out.print(vertex + " ");
            }
            System.out.println();
        }
    }

    // Getter for adjacency list (for use in algorithms)
    public LinkedList<Integer>[] getAdjList() {
        return adjList;
    }
}

Breaking Down the Graph Class

1. Vertices and Adjacency List:

• vertices is the number of vertices in the graph.
• adjList is an array of linked lists to store adjacent vertices.

1. Constructor:

• Initializes the vertices and creates a linked list for each vertex.

1. addEdge Method:

• Adds an edge between two vertices for an undirected graph.

1. printGraph Method:

• Prints the adjacency list of the graph.

Breadth-First Search (BFS)

BFS is a traversal algorithm that explores all neighbors at the present depth before moving on to nodes at the next depth level. Here’s the BFS class:

// Breadth-First Search
public class BFS {
    private boolean[] visited; // Array to track visited vertices

    // Constructor to perform BFS from a start vertex
    public BFS(Graph graph, int startVertex) {
        visited = new boolean[graph.getAdjList().length];
        System.out.print("BFS Traversal starting from vertex " + startVertex + ": ");
        bfs(graph, startVertex);
        System.out.println();
    }

    // BFS function
    private void bfs(Graph graph, int startVertex) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(startVertex);
        visited[startVertex] = true;

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

            for (int adjacentVertex : graph.getAdjList()[vertex]) {
                if (!visited[adjacentVertex]) {
                    visited[adjacentVertex] = true;
                    queue.add(adjacentVertex);
                }
            }
        }
    }
}

Breaking Down the BFS Class

1. Visited Array:

• Keeps track of visited vertices to avoid cycles.

1. Constructor:

• Initializes the visited array and starts the BFS traversal from the given start vertex.

1. bfs Method:

• Uses a queue to explore all neighbors at the current depth level.

Example Program

Let’s combine the Graph and BFS classes in an example program:

public class BFSExample {
    public static void main(String[] args) {
        // Create a graph with 5 vertices
        Graph graph = new Graph(5);

        // Add edges to the graph
        graph.addEdge(0, 1);
        graph.addEdge(0, 4);
        graph.addEdge(1, 3);
        graph.addEdge(1, 4);
        graph.addEdge(2, 3);
        graph.addEdge(3, 4);

        // Print the graph's adjacency list
        System.out.println("Graph adjacency list:");
        graph.printGraph();

        // Perform BFS starting from vertex 0
        new BFS(graph, 0);
    }
}

Running the Example Program

1. Create a Graph:

• The graph is created with 5 vertices.

1. Add Edges:

• Edges are added between vertices.

1. Print Adjacency List:

• The adjacency list of the graph is printed.

1. Perform BFS:

• BFS traversal starts from vertex 0.

Conclusion

In this blog post, we learned how to represent a graph using an adjacency list and implemented the BFS traversal algorithm. We also walked through an example program to see BFS in action. Understanding this concept and its implementation is essential for tackling more complex graph-related problems in computer science. Happy coding!