Understanding Graph Traversal: Implementing BFS and DFS in Java

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

Graph Representation

Before diving into the traversal algorithms, 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.

Depth-First Search (DFS)

DFS is a traversal algorithm that explores as far as possible along each branch before backtracking. Here’s the DFS class:

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

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

    // Recursive DFS function
    private void dfs(Graph graph, int vertex) {
        visited[vertex] = true;
        System.out.print(vertex + " ");

        for (int adjacentVertex : graph.getAdjList()[vertex]) {
            if (!visited[adjacentVertex]) {
                dfs(graph, adjacentVertex);
            }
        }
    }
}

Breaking Down the DFS Class

1. Visited Array:

• Keeps track of visited vertices to avoid cycles.

1. Constructor:

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

1. dfs Method:

• Recursively visits all the adjacent vertices.

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, DFS, and BFS classes in an example program:

public class GraphTraversalExample {
    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 DFS starting from vertex 0
        new DFS(graph, 0);

        // 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 DFS and BFS:

• Both DFS and BFS traversals start from vertex 0.

Conclusion

In this blog post, we learned how to represent a graph using an adjacency list and implemented two fundamental graph traversal algorithms: DFS and BFS. We also walked through an example program to see these algorithms in action. Understanding these concepts and their implementations is essential for tackling more complex graph-related problems in computer science. Happy coding!