Search⌘ K
AI Features
Home
Courses
Learn Data Structures and Algorithms in Java

Graph Traversals

Explore graph traversal methods such as breadth-first search and depth-first search in Java. Understand how these algorithms systematically visit nodes, their time and space complexities, and their practical applications in solving graph problems.

We'll cover the following...

Graph traversal is the process of visiting all vertices (nodes) in a graph systematically. It is a fundamental concept because many graph algorithms rely on efficient graph exploration.

The two most common graph traversal techniques are:

  • Breadth-first search (BFS)

  • Depth-first search (DFS)

Breadth-first search (BFS)

Breadth-First Search explores a graph level by level. Starting from a chosen node, it first visits all immediate neighbors before moving to nodes at the next level.

Key idea

BFS uses a queue (FIFO: first in, first out).

How BFS works

  1. Start from a chosen node.

  2. Mark it as visited.

  3. Add it to a queue.

  4. While the queue is not empty:

    1. Dequeue a node.

    2. Visit all its unvisited neighbors.

    3. Mark them as visited and add them to the queue.

Below is the Java implementation of BFS:

Java 25
import java.util.*;
class Graph {
    private Map<String, List<String>> graph;   // Adjacency list
    public Graph() {
        this.graph = new HashMap<>();
    }
    public void addEdge(String u, String v) {
        // Initialize nodes if not present
        graph.putIfAbsent(u, new ArrayList<>());
        graph.putIfAbsent(v, new ArrayList<>());
        graph.get(u).add(v);
        graph.get(v).add(u);   // Remove for directed graph
    }
    public void bfs(String start) {
        Set<String> visited = new HashSet<>();
        Queue<String> queue = new LinkedList<>();
        queue.add(start);
        visited.add(start);   // Mark start node as visited
        while (!queue.isEmpty()) {
            String vertex = queue.poll();   // Get next node
            System.out.print(vertex + " ");
            for (String neighbor : graph.get(vertex)) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);    // Mark neighbor visited
                    queue.add(neighbor);      // Add neighbor to queue
                }
            }
        }
    }
}
public class Main {
    public static void main(String[] args) {
        Graph g = new Graph();
        // Build graph
        g.addEdge("A", "B");
        g.addEdge("A", "C");
        g.addEdge("B", "D");
        g.addEdge("B", "E");
        g.addEdge("C", "F");
        // Run BFS
        g.bfs("A");
    }
}
Graph BFS

Time complexity:
The time complexity of BFS is ...