java 37 lines · 7 steps

Breadth-first search on an adjacency-list graph

An undirected graph backed by a HashMap, traversed level by level with a queue.

Explained by highlit
Intermediate graph-traversal bfs adjacency-list queue visited-set
1import java.util.ArrayDeque;
2import java.util.ArrayList;
3import java.util.HashMap;
4import java.util.HashSet;
5import java.util.List;
6import java.util.Map;
7import java.util.Queue;
8import java.util.Set;
9 
10public class Graph {
11 private final Map<Integer, List<Integer>> adjacency = new HashMap<>();
12 
13 public void addEdge(int from, int to) {
14 adjacency.computeIfAbsent(from, k -> new ArrayList<>()).add(to);
15 adjacency.computeIfAbsent(to, k -> new ArrayList<>()).add(from);
16 }
17 
18 public List<Integer> bfs(int start) {
19 List<Integer> order = new ArrayList<>();
20 Set<Integer> visited = new HashSet<>();
21 Queue<Integer> queue = new ArrayDeque<>();
22 
23 queue.add(start);
24 visited.add(start);
25 
26 while (!queue.isEmpty()) {
27 int node = queue.poll();
28 order.add(node);
29 for (int neighbor : adjacency.getOrDefault(node, List.of())) {
30 if (visited.add(neighbor)) {
31 queue.add(neighbor);
32 }
33 }
34 }
35 return order;
36 }
37}
01 / 01
STEP 01

Walkthrough

Space play ←→ step click any line
Three takeaways
  1. 1An adjacency map of node to neighbor list is a compact, flexible way to represent sparse graphs.
  2. 2BFS visits nodes in distance order by processing a FIFO queue and marking nodes the moment they're enqueued.
  3. 3Set.add returning a boolean lets you check membership and record it in one branchless step.

Related explainers

java 
public class ThumbnailProcessor {
 
    private static final int MAX_CONCURRENCY = 4;
 

Bounded parallel thumbnail rendering in Java

concurrency thread-pool futures
Intermediate 7 steps
java 
public class SortedListMerger {
 
    public static int[] merge(int[] a, int[] b) {
        int[] result = new int[a.length + b.length];

Merging two sorted arrays in Java

two-pointers merging arrays
Beginner 6 steps
java 
import java.util.ArrayDeque;
import java.util.Deque;
 
public final class RollingAverage {

A rolling average over a sliding window

sliding-window running-sum deque
Intermediate 7 steps
java 
@Target({ElementType.FIELD, ElementType.PARAMETER})
@Retention(RetentionPolicy.RUNTIME)
@Constraint(validatedBy = StrongPasswordValidator.class)
@Documented

Building a custom @StrongPassword validator in Spring

bean-validation annotations regex
Intermediate 7 steps
java 
@Component
public class JwtAuthenticationFilter extends OncePerRequestFilter {
 
    private final JwtTokenProvider tokenProvider;

How a JWT auth filter works in Spring

authentication jwt servlet-filter
Intermediate 8 steps
java 
@Entity
@Table(name = "accounts")
public class Account {
 

Optimistic locking with @Version in Spring

optimistic-locking jpa concurrency
Advanced 7 steps

Share this explainer

Here's the card — post it anywhere.

Breadth-first search on an adjacency-list graph — share card
Made with highlit — turn any snippet into a walkthrough like this in about a minute.
Explain your code