Graphs in Java: BFS and DFS

A city bus map shows stops as dots and roads between them as lines. Some stops connect to many others, some to only one, and you can often reach the same stop by several routes. Friend lists on a social app, links between web pages, and prerequisites between school subjects all have the same shape. This shape is called a graph, and two simple ways of walking through it, breadth-first search and depth-first search, solve a surprising number of problems: finding the shortest route, checking whether two places are connected, or spotting a loop. In this lesson, you will learn how to store a graph in Java and write both searches.

What Is a Graph?

A graph in Java is a data structure that is used to represent connections: a set of vertices (also called nodes) and a set of edges, where each edge joins two vertices.

A tree is a special graph: connected, with no cycles.

Storing a Graph: Adjacency List

The most common way to store a graph is an adjacency list: for each vertex, a list of its neighbors. In Java, a Map<String, List<String>> does the job.

BFS and DFS

• Breadth-first search (BFS) visits the start, then all its neighbors, then all their neighbors, and so on, level by level. It uses a queue.
• Depth-first search (DFS) goes from the start to a neighbor, then to that neighbor's neighbor, as deep as possible, and backs up only at a dead end. It uses a stack, usually the call stack through recursion.

Both keep a visited set, so that no vertex is processed twice. Without it, a cycle would make them loop forever.

Building the Graph and Searching It

Let's see an example that builds the graph from the picture and runs both searches from A.

import java.util.*;
 
public class Graph {
    private final Map<String, List<String>> adj = new LinkedHashMap<>();
 
    void addEdge(String a, String b) {               // undirected
        adj.computeIfAbsent(a, k -> new ArrayList<>()).add(b);
        adj.computeIfAbsent(b, k -> new ArrayList<>()).add(a);
    }
 
    List<String> bfs(String start) {
        List<String> order = new ArrayList<>();
        Set<String> visited = new HashSet<>(List.of(start));
        Queue<String> queue = new ArrayDeque<>(List.of(start));
        while (!queue.isEmpty()) {
            String v = queue.poll();
            order.add(v);
            for (String n : adj.get(v)) {
                if (visited.add(n)) {                // true if newly added
                    queue.offer(n);
                }
            }
        }
        return order;
    }
 
    List<String> dfs(String start) {
        List<String> order = new ArrayList<>();
        dfs(start, new HashSet<>(), order);
        return order;
    }
 
    private void dfs(String v, Set<String> visited, List<String> order) {
        visited.add(v);
        order.add(v);
        for (String n : adj.get(v)) {
            if (!visited.contains(n)) {
                dfs(n, visited, order);              // go deeper first
            }
        }
    }
 
    public static void main(String[] args) {
        Graph g = new Graph();
        String[][] edges = {{"A", "B"}, {"A", "C"}, {"B", "D"}, {"C", "D"},
                            {"C", "E"}, {"D", "F"}, {"E", "F"}};
        for (String[] e : edges) {
            g.addEdge(e[0], e[1]);
        }
        System.out.println("neighbors: " + g.adj);
        System.out.println("BFS from A: " + g.bfs("A"));
        System.out.println("DFS from A: " + g.dfs("A"));
    }
}

neighbors: {A=[B, C], B=[A, D], C=[A, D, E], D=[B, C, F], E=[C, F], F=[D, E]}
BFS from A: [A, B, C, D, E, F]
DFS from A: [A, B, D, C, E, F]

Explanation:

1. addEdge adds each vertex to the other's list, because the graph is undirected. computeIfAbsent creates the list the first time a vertex appears.
2. BFS takes vertices from the front of the queue and adds unvisited neighbors to the back. A is first, then its neighbors B and C, then D (from B) and E (from C), then F.
3. A vertex is marked visited when it is added to the queue, not when it is taken out. Otherwise D would be queued twice, once from B and once from C.
4. DFS visits A, then its first neighbor B, then B's first unvisited neighbor D, then D's first unvisited neighbor C, then E, then F. It goes deep before it goes wide.

Shortest Path with BFS

In an unweighted graph, BFS reaches every vertex by the fewest possible edges, because it finishes each level before starting the next. Recording each vertex's distance and parent gives the shortest path.

import java.util.*;
 
public class ShortestRoute {
    public static void main(String[] args) {
        Map<String, List<String>> adj = Map.of(
                "School", List.of("Library", "Park"),
                "Library", List.of("School", "Market"),
                "Park", List.of("School", "Market", "Temple"),
                "Market", List.of("Library", "Park", "Home"),
                "Temple", List.of("Park", "Home"),
                "Home", List.of("Market", "Temple"));
 
        Map<String, String> parent = new HashMap<>();
        Map<String, Integer> distance = new HashMap<>(Map.of("School", 0));
        Queue<String> queue = new ArrayDeque<>(List.of("School"));
        while (!queue.isEmpty()) {
            String v = queue.poll();
            for (String n : adj.get(v)) {
                if (!distance.containsKey(n)) {
                    distance.put(n, distance.get(v) + 1);
                    parent.put(n, v);
                    queue.offer(n);
                }
            }
        }
 
        LinkedList<String> path = new LinkedList<>();
        for (String at = "Home"; at != null; at = parent.get(at)) {
            path.addFirst(at);
        }
        System.out.println("stops to Home: " + distance.get("Home"));
        System.out.println("route: " + String.join(" -> ", path));
    }
}

stops to Home: 3
route: School -> Library -> Market -> Home

Explanation: BFS from School records, for every place, how many edges away it is and which place it was reached from. Walking the parent links backwards from Home and adding each place to the front gives the route. School, Park, Temple, Home is just as short; BFS returns the first shortest route it finds. For weighted graphs (roads of different lengths), use Dijkstra's algorithm, which replaces the queue with a PriorityQueue.

Complexity

Interview Corner

Practice

1. Easy: Add the edge {"B", "E"} to Graph.java. Predict the new BFS and DFS orders, then run it.
2. Harder: Write boolean connected(String a, String b) using BFS, and int components() that counts connected groups. Test it after adding two vertices X and Y joined only to each other.

Key Takeaways