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 
  public static List<Integer> sort(int numNodes, int[][] edges) {
      List<List<Integer>> adjacency = new ArrayList<>();
      for (int i = 0; i < numNodes; i++) {
          adjacency.add(new ArrayList<>());
      }
      int[] inDegree = new int[numNodes];
      for (int[] edge : edges) {
          adjacency.get(edge[0]).add(edge[1]);
          inDegree[edge[1]]++;
      }
15 
      Queue<Integer> ready = new ArrayDeque<>();
      for (int node = 0; node < numNodes; node++) {
          if (inDegree[node] == 0) {
              ready.offer(node);
          }
      }
22 
      List<Integer> order = new ArrayList<>();
      while (!ready.isEmpty()) {
          int node = ready.poll();
          order.add(node);
          for (int neighbor : adjacency.get(node)) {
              if (--inDegree[neighbor] == 0) {
                  ready.offer(neighbor);
              }
          }
      }
33 
      if (order.size() != numNodes) {
          throw new IllegalArgumentException("Graph has a cycle; no topological order exists");
      }
      return order;
  }
39}

01 / 01

STEP 01

Walkthrough

Space play ←→ step click any line

Three takeaways

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

Related explainers

java

@Component
@Converter
public class EncryptedStringConverter implements AttributeConverter<String, String> {

Transparent column encryption in Spring & JPA

encryption aes-gcm jpa-converter

Advanced 10 steps

java

package com.acme.billing.config;
 
import org.springframework.boot.autoconfigure.condition.ConditionalOnProperty;
import org.springframework.boot.context.properties.ConfigurationProperties;

Feature-flagged beans with Spring @ConditionalOnProperty

feature-flags conditional-beans strategy-pattern

Intermediate 5 steps

java

public static Map<String, String> parseCookieHeader(String header) {
    Map<String, String> cookies = new LinkedHashMap<>();
    if (header == null || header.isBlank()) {
        return cookies;

Parsing an HTTP Cookie header in Java

string-parsing http url-decoding

Intermediate 6 steps

java

public class TimedSocketReader {
 
    private static final int READ_TIMEOUT_MS = 5_000;
    private static final int CONNECT_TIMEOUT_MS = 3_000;

Reading a socket with connect and read timeouts

sockets timeouts io

Intermediate 8 steps

java

public final class EncodingDetector {
 
    public enum Encoding {
        UTF_8, UTF_16LE, UTF_16BE, UTF_32LE, UTF_32BE, ASCII, UNKNOWN

Detecting text encoding from raw bytes in Java

byte-manipulation encoding-detection bitwise-operations

Intermediate 8 steps

java

public final class ImportOrganizer {
 
    private static final Pattern IMPORT_LINE =
            Pattern.compile("^import\\s+(static\\s+)?([\\w.]+(?:\\.\\*)?)\\s*;\\s*$");