java 39 lines · 6 steps

Topological sort with Kahn's algorithm

Order a directed graph's nodes so every edge points forward, using in-degree counting and a ready queue.

Explained by highlit
Intermediate graphs topological-sort bfs in-degree algorithms
1import java.util.*;
2 
3public class TopologicalSort {
4 
5 public static List<Integer> sort(int numNodes, int[][] edges) {
6 List<List<Integer>> adjacency = new ArrayList<>();
7 for (int i = 0; i < numNodes; i++) {
8 adjacency.add(new ArrayList<>());
9 }
10 int[] inDegree = new int[numNodes];
11 for (int[] edge : edges) {
12 adjacency.get(edge[0]).add(edge[1]);
13 inDegree[edge[1]]++;
14 }
15 
16 Queue<Integer> ready = new ArrayDeque<>();
17 for (int node = 0; node < numNodes; node++) {
18 if (inDegree[node] == 0) {
19 ready.offer(node);
20 }
21 }
22 
23 List<Integer> order = new ArrayList<>();
24 while (!ready.isEmpty()) {
25 int node = ready.poll();
26 order.add(node);
27 for (int neighbor : adjacency.get(node)) {
28 if (--inDegree[neighbor] == 0) {
29 ready.offer(neighbor);
30 }
31 }
32 }
33 
34 if (order.size() != numNodes) {
35 throw new IllegalArgumentException("Graph has a cycle; no topological order exists");
36 }
37 return order;
38 }
39}
01 / 01
STEP 01

Walkthrough

Space play ←→ step click any line
Three takeaways
  1. 1Kahn's algorithm repeatedly removes nodes with no remaining prerequisites to build a valid ordering.
  2. 2Tracking in-degree lets you detect exactly when a node becomes ready without rescanning the graph.
  3. 3If fewer nodes are emitted than exist, the graph must contain a cycle and no ordering is possible.

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.

Topological sort with Kahn's algorithm — share card
Made with highlit — turn any snippet into a walkthrough like this in about a minute.
Explain your code