JAVA-205 · Lesson 8 of 12 · 23 min

Breadth-first and depth-first search

▶ Video coming soon A video version of this lesson is on the way.

With the pickup map stored as an adjacency list, Kofi's first questions are not about minutes at all. Which sites can the cargo bike reach from the shop? Which can be reached with the fewest stops along the way? If a road is closed for the Santa Claus parade, is every site still reachable? On Tuesday, November 9, 2027, Ingrid shows Hamza the two basic ways to explore a graph, which answer all three: breadth-first search and depth-first search. Every more advanced graph algorithm, including the shortest-path method of the next lesson, is built on one of them.

Exploring a graph

Both searches start at one vertex and visit every vertex that can be reached from it, each exactly once. Both keep a set of vertices already visited, so that cycles in the graph, such as the triangle between three places that are all joined to each other, do not send them round in circles forever. They differ only in which vertex they explore next. Breadth-first search explores in order of distance from the start, like ripples spreading on a pond. Depth-first search follows one path as far as it can before backing up and trying another, like walking a maze with one hand on the wall.

Breadth-first search (BFS) uses a queue. Put the start vertex in the queue and mark it visited. Then, while the queue is not empty, take the vertex at the front and add each of its neighbors that has not been visited to the back of the queue, marking it visited as you add it. Because the queue is first in, first out, all the vertices one edge from the start are processed before any vertex two edges away, and so on. That makes BFS give the fewest edges from the start to every vertex, which in the pickup map is the fewest stops.

Java Example · Main.java
import java.util.*;

public class Main {
    static Map<String, List<String>> graph() {
        String[][] roads = {{"Shop", "German Village"}, {"Shop", "Bexley"}, {"German Village", "Bexley"}, {"German Village", "Short North"}, {"Shop", "Short North"},
                {"Short North", "Grandview"}, {"Grandview", "Hilltop"}, {"Short North", "Hilltop"}, {"Bexley", "Clintonville"}, {"Shop", "Clintonville"}};
        Map<String, List<String>> g = new LinkedHashMap<>();
        for (String[] r : roads) {
            g.computeIfAbsent(r[0], k -> new ArrayList<>()).add(r[1]);
            g.computeIfAbsent(r[1], k -> new ArrayList<>()).add(r[0]);
        }
        return g;
    }

    public static void main(String[] args) {
        Map<String, List<String>> g = graph();
        Map<String, Integer> hops = new LinkedHashMap<>();
        Deque<String> queue = new ArrayDeque<>();
        hops.put("Shop", 0);
        queue.add("Shop");
        while (!queue.isEmpty()) {
            String place = queue.poll();
            for (String next : g.get(place)) {
                if (!hops.containsKey(next)) {
                    hops.put(next, hops.get(place) + 1);
                    queue.add(next);
                }
            }
        }
        hops.forEach((place, h) -> System.out.println(place + ": " + h + " road" + (h == 1 ? "" : "s")));
    }
}
Output
Shop: 0 roads
German Village: 1 road
Bexley: 1 road
Short North: 1 road
Clintonville: 1 road
Grandview: 2 roads
Hilltop: 2 roads

What this code does

The map hops doubles as the visited set: a place is marked visited by recording its distance when it first joins the queue. The ArrayDeque is used as a first-in, first-out queue with add and poll. Every place is one road from the Shop except Grandview and Hilltop, which need two.

The pickup graph drawn as rings around the Shop. The center ring is the Shop at distance 0. The first ring holds German Village, Bexley, Short North and Clintonville at distance 1. The outer ring holds Grandview and Hilltop at distance 2. The edges BFS used to discover each place are drawn thick; the other roads are thin and gray.
Breadth-first search finds places in rings of increasing distance from the start

Marking a vertex visited when it is added to the queue, not when it is taken out, matters. If you wait until it is taken out, the same vertex can be added several times by different neighbors before it is processed, which wastes time and, in a dense graph, a lot of memory.

Recovering the path

Knowing that Hilltop is two roads away is useful; knowing which two roads is more useful. BFS can record, for each vertex, the vertex it was discovered from, its parent. The parents form a tree rooted at the start, the BFS tree, and following parent links back from any vertex to the start, then reversing, gives a path with the fewest edges.

Java Example · Main.java
import java.util.*;

public class Main {
    static Map<String, List<String>> graph() {
        String[][] roads = {{"Shop", "German Village"}, {"Shop", "Bexley"}, {"German Village", "Bexley"}, {"German Village", "Short North"}, {"Shop", "Short North"},
                {"Short North", "Grandview"}, {"Grandview", "Hilltop"}, {"Short North", "Hilltop"}, {"Bexley", "Clintonville"}, {"Shop", "Clintonville"}};
        Map<String, List<String>> g = new LinkedHashMap<>();
        for (String[] r : roads) {
            g.computeIfAbsent(r[0], k -> new ArrayList<>()).add(r[1]);
            g.computeIfAbsent(r[1], k -> new ArrayList<>()).add(r[0]);
        }
        return g;
    }

    static List<String> fewestStops(Map<String, List<String>> g, String from, String to) {
        Map<String, String> parent = new HashMap<>();
        Deque<String> queue = new ArrayDeque<>(List.of(from));
        parent.put(from, null);
        while (!queue.isEmpty()) {
            String place = queue.poll();
            if (place.equals(to)) break;
            for (String next : g.get(place)) {
                if (!parent.containsKey(next)) {
                    parent.put(next, place);
                    queue.add(next);
                }
            }
        }
        if (!parent.containsKey(to)) return List.of();
        LinkedList<String> path = new LinkedList<>();
        for (String p = to; p != null; p = parent.get(p)) path.addFirst(p);
        return path;
    }

    public static void main(String[] args) {
        Map<String, List<String>> g = graph();
        System.out.println(fewestStops(g, "Shop", "Hilltop"));
        System.out.println(fewestStops(g, "Clintonville", "Grandview"));
    }
}
Output
[Shop, Short North, Hilltop]
[Clintonville, Shop, Short North, Grandview]

What this code does

parent records where each place was first reached from, and the search stops early once the destination is taken from the queue. Walking the parent links back from the destination and adding each place to the front of a list gives the route in the right order. The HashMap's iteration order never matters here, because the program only looks up keys in it.

BFS finds the path with the fewest edges, not the quickest. Its route from the Shop to Hilltop goes through Short North, two roads but 49 minutes. A route through German Village, Short North and Grandview has four roads but only 45 minutes. For weights you need the next lesson's algorithm, which is BFS with the queue replaced by a priority queue.

Depth-first search (DFS) uses a stack instead of a queue: always explore from the most recently discovered vertex. Written recursively, it is very short: visit a vertex, then for each neighbor not yet visited, search from that neighbor. The call stack is the stack. DFS does not find shortest paths, but it is the basis for many other algorithms: finding connected components, detecting cycles, topological sorting and solving mazes and puzzles.

Java Example · Main.java
import java.util.*;

public class Main {
    static Map<String, List<String>> graph() {
        String[][] roads = {{"Shop", "German Village"}, {"Shop", "Bexley"}, {"German Village", "Bexley"}, {"German Village", "Short North"}, {"Shop", "Short North"},
                {"Short North", "Grandview"}, {"Grandview", "Hilltop"}, {"Short North", "Hilltop"}, {"Bexley", "Clintonville"}, {"Shop", "Clintonville"}};
        Map<String, List<String>> g = new LinkedHashMap<>();
        for (String[] r : roads) {
            g.computeIfAbsent(r[0], k -> new ArrayList<>()).add(r[1]);
            g.computeIfAbsent(r[1], k -> new ArrayList<>()).add(r[0]);
        }
        return g;
    }

    static void dfs(Map<String, List<String>> g, String place, Set<String> visited, String indent) {
        visited.add(place);
        System.out.println(indent + place);
        for (String next : g.get(place)) {
            if (!visited.contains(next)) dfs(g, next, visited, indent + "  ");
        }
    }

    public static void main(String[] args) {
        dfs(graph(), "Shop", new LinkedHashSet<>(), "");
    }
}
Output
Shop
  German Village
    Bexley
      Clintonville
    Short North
      Grandview
        Hilltop

What this code does

The recursive search visits a place and then goes deeper into each neighbor it has not seen, so the indentation shows how far each place is down the current path. From the Shop it dives through German Village and Bexley to Clintonville before backing up. The order depends on the order of each adjacency list, which the LinkedHashMap keeps fixed.

Recursive DFS goes as deep as the longest path it explores, which in a large graph can be thousands of vertices: enough for the StackOverflowError of lesson 5. The safe version uses an explicit ArrayDeque as the stack, with push and pop. To visit neighbors in the same order as the recursive version, push them in reverse order, because the last one pushed is popped first.

Java Example · Main.java
import java.util.*;

public class Main {
    static Map<String, List<String>> graph() {
        String[][] roads = {{"Shop", "German Village"}, {"Shop", "Bexley"}, {"German Village", "Bexley"}, {"German Village", "Short North"}, {"Shop", "Short North"},
                {"Short North", "Grandview"}, {"Grandview", "Hilltop"}, {"Short North", "Hilltop"}, {"Bexley", "Clintonville"}, {"Shop", "Clintonville"}};
        Map<String, List<String>> g = new LinkedHashMap<>();
        for (String[] r : roads) {
            g.computeIfAbsent(r[0], k -> new ArrayList<>()).add(r[1]);
            g.computeIfAbsent(r[1], k -> new ArrayList<>()).add(r[0]);
        }
        return g;
    }

    public static void main(String[] args) {
        Map<String, List<String>> g = graph();
        Set<String> visited = new LinkedHashSet<>();
        Deque<String> stack = new ArrayDeque<>();
        stack.push("Shop");
        while (!stack.isEmpty()) {
            String place = stack.pop();
            if (!visited.add(place)) continue;
            List<String> next = g.get(place);
            for (int i = next.size() - 1; i >= 0; i--) {
                if (!visited.contains(next.get(i))) stack.push(next.get(i));
            }
        }
        System.out.println("DFS order: " + visited);
    }
}
Output
DFS order: [Shop, German Village, Bexley, Clintonville, Short North, Grandview, Hilltop]

What this code does

The loop pops the most recent place, skips it if it has already been visited, and pushes its unvisited neighbors in reverse so the first neighbor is explored first. A place can be pushed more than once before it is popped, which is why visited.add is checked on pop. The order matches the recursive search, with no risk of overflowing the call stack.

BFS and DFS compared
Breadth-first searchDepth-first search
FrontierQueue: first in, first outStack or recursion: last in, first out
VisitsIn order of distance from the startDown one path, then backs up
Finds fewest-edge paths?YesNo
Typical usesFewest stops, levels, nearest matchComponents, cycles, topological order, mazes
TimeO(V + E)O(V + E)
Extra memoryO(V) for the queue and visited setO(V) for the stack and visited set

Both searches are O(V + E) with an adjacency list: every vertex is added and removed once, and every edge is looked at once from each end. With an adjacency matrix they become O(V²), because finding a vertex's neighbors means reading a whole row.

Connected components

In January 2028 two new partner sites, Worthington and Westerville, join the pickup scheme. There is no cargo-bike road from them to the rest yet; they are close only to each other, and a volunteer with a car will collect from them once a month. The graph now has two connected components: groups of vertices that can reach each other but not the rest. Running a search from every vertex not yet visited, and numbering each new search, labels the components.

Java Example · Main.java
import java.util.*;

public class Main {
    static Map<String, List<String>> graph() {
        String[][] roads = {{"Shop", "German Village"}, {"Shop", "Bexley"}, {"German Village", "Bexley"}, {"German Village", "Short North"}, {"Shop", "Short North"},
                {"Short North", "Grandview"}, {"Grandview", "Hilltop"}, {"Short North", "Hilltop"}, {"Bexley", "Clintonville"}, {"Shop", "Clintonville"}};
        Map<String, List<String>> g = new LinkedHashMap<>();
        for (String[] r : roads) {
            g.computeIfAbsent(r[0], k -> new ArrayList<>()).add(r[1]);
            g.computeIfAbsent(r[1], k -> new ArrayList<>()).add(r[0]);
        }
        return g;
    }

    public static void main(String[] args) {
        Map<String, List<String>> g = graph();
        g.put("Worthington", new ArrayList<>(List.of("Westerville")));
        g.put("Westerville", new ArrayList<>(List.of("Worthington")));

        Map<String, Integer> component = new LinkedHashMap<>();
        int count = 0;
        for (String start : g.keySet()) {
            if (component.containsKey(start)) continue;
            count++;
            Deque<String> queue = new ArrayDeque<>(List.of(start));
            component.put(start, count);
            while (!queue.isEmpty()) {
                for (String next : g.get(queue.poll())) {
                    if (component.putIfAbsent(next, count) == null) queue.add(next);
                }
            }
        }
        System.out.println(count + " components: " + component);
    }
}
Output
2 components: {Shop=1, German Village=1, Bexley=1, Short North=1, Clintonville=1, Grandview=1, Hilltop=1, Worthington=2, Westerville=2}

What this code does

The outer loop starts a breadth-first search from each place that has no component number yet, and every place that search reaches gets the same number. putIfAbsent returns null only the first time a place is labeled, which doubles as the visited check. The seven cargo-bike places form component 1 and the two new sites form component 2.

The same method answers the parade question: remove the closed roads from the adjacency lists, run the components search again, and if the count rises above one, some sites can no longer be reached by cargo bike.

Try it yourself

Stops from a site

Complete hops(Map<String, List<String>> g, String from) with a breadth-first search that returns a map from each reachable place to the number of roads on the fewest-stop route from from.

Starting from Hilltop, the program should print {Hilltop=0, Grandview=1, Short North=1, German Village=2, Shop=2, Bexley=3, Clintonville=3}.

import java.util.*;

public class Main {
    static Map<String, List<String>> graph() {
        String[][] roads = {{"Shop", "German Village"}, {"Shop", "Bexley"}, {"German Village", "Bexley"}, {"German Village", "Short North"}, {"Shop", "Short North"},
                {"Short North", "Grandview"}, {"Grandview", "Hilltop"}, {"Short North", "Hilltop"}, {"Bexley", "Clintonville"}, {"Shop", "Clintonville"}};
        Map<String, List<String>> g = new LinkedHashMap<>();
        for (String[] r : roads) {
            g.computeIfAbsent(r[0], k -> new ArrayList<>()).add(r[1]);
            g.computeIfAbsent(r[1], k -> new ArrayList<>()).add(r[0]);
        }
        return g;
    }

    static Map<String, Integer> hops(Map<String, List<String>> g, String from) {
        Map<String, Integer> dist = new LinkedHashMap<>();
        dist.put(from, 0);
        for (String next : g.get(from)) dist.put(next, 1);
        return dist;
    }

    public static void main(String[] args) {
        System.out.println(hops(graph(), "Hilltop"));
    }
}

Try it yourself

Can we still get there?

Write reachable(Map<String, List<String>> g, String from, String to) with a depth-first search using an explicit ArrayDeque stack. Then the program removes the road between Short North and Grandview and the road between Short North and Hilltop (closed for the parade) and checks again.

The program should print before: true and after: false.

import java.util.*;

public class Main {
    static Map<String, List<String>> graph() {
        String[][] roads = {{"Shop", "German Village"}, {"Shop", "Bexley"}, {"German Village", "Bexley"}, {"German Village", "Short North"}, {"Shop", "Short North"},
                {"Short North", "Grandview"}, {"Grandview", "Hilltop"}, {"Short North", "Hilltop"}, {"Bexley", "Clintonville"}, {"Shop", "Clintonville"}};
        Map<String, List<String>> g = new LinkedHashMap<>();
        for (String[] r : roads) {
            g.computeIfAbsent(r[0], k -> new ArrayList<>()).add(r[1]);
            g.computeIfAbsent(r[1], k -> new ArrayList<>()).add(r[0]);
        }
        return g;
    }

    static boolean reachable(Map<String, List<String>> g, String from, String to) {
        return g.containsKey(to);
    }

    public static void main(String[] args) {
        Map<String, List<String>> g = graph();
        System.out.println("before: " + reachable(g, "Shop", "Hilltop"));
        g.get("Short North").removeAll(List.of("Grandview", "Hilltop"));
        g.get("Grandview").remove("Short North");
        g.get("Hilltop").remove("Short North");
        System.out.println("after: " + reachable(g, "Shop", "Hilltop"));
    }
}

Common mistakes

  • MistakeForgetting the visited set.

    InsteadMark vertices visited, or cycles make the search loop forever.

  • MistakeMarking a vertex visited only when it is taken out of the BFS queue.

    InsteadMark it when it is added, so it is queued once.

  • MistakeUsing BFS to find the quickest route in a weighted graph.

    InsteadBFS finds the fewest edges; use Dijkstra's algorithm for weights.

  • MistakeWriting recursive DFS for graphs that may have very long paths.

    InsteadUse an explicit ArrayDeque stack to avoid StackOverflowError.

  • MistakeExpecting a search from one vertex to reach every vertex.

    InsteadRun a search from each unvisited vertex to cover every component.

Summary and key terms

  • Breadth-first search and depth-first search both visit every vertex reachable from a start vertex exactly once, using a visited set to cope with cycles.
  • BFS keeps a queue, explores in order of distance and finds paths with the fewest edges; recording each vertex's parent lets you rebuild the path.
  • DFS follows one path as deep as it can, then backs up; it is short to write recursively, but an explicit ArrayDeque stack avoids stack overflow on deep graphs.
  • Both run in O(V + E) with an adjacency list.
  • Running a search from every unvisited vertex finds the connected components, which shows whether every site can still be reached when roads close.
  • BFS ignores weights, so the quickest route needs the next lesson's shortest-path algorithm.
Graph search
A systematic way of visiting every vertex reachable from a start.
Visited set
The vertices a search has already reached, kept to avoid repeating work.
Breadth-first search
A search that uses a queue and visits vertices in order of distance from the start.
Depth-first search
A search that uses a stack and follows each path as deep as possible before backing up.
Frontier
The vertices discovered but not yet explored, held in the queue or stack.
Parent
The vertex from which a search first reached a given vertex.
BFS tree
The tree formed by the parent links of a breadth-first search.
Connected component
A largest group of vertices in which every vertex can reach every other.

Practice problems

Work each problem on paper first, then reveal the answer to check.

  1. Which data structure does breadth-first search use for its frontier?

    Show answer

    A queue.

  2. Why does BFS find the route with the fewest stops?

    Show answer

    It processes every vertex one edge away before any vertex two edges away, and so on.

  3. What is the running time of BFS and DFS with an adjacency list?

    Show answer

    O(V + E).

  4. Why might recursive DFS fail on a very large graph?

    Show answer

    The recursion can get deep enough to overflow the call stack.

  5. How do you count the connected components of a graph?

    Show answer

    Start a new search from each vertex not yet visited and count the searches.

Lesson quiz · 5 questions

Score 60% or more to complete this lesson.

Take the quiz