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

public interface GitHubClient {
 
    @GetExchange("/users/{username}")
    GitHubUser getUser(@PathVariable String username);

Declarative HTTP clients in Spring

http-client declarative-api proxy

Intermediate 8 steps

java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

Building a trie for autocomplete in Java

trie prefix-tree recursion

Intermediate 8 steps

java

@RestController
@RequestMapping("/api/products")
public class ProductSearchController {

Binding collection query params in Spring

rest-api query-parameters dependency-injection

Intermediate 6 steps

java

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Map;

Evaluating math expressions with two stacks

stacks parsing operator-precedence

Intermediate 9 steps

java

@Entity
@Table(name = "orders")
@SQLDelete(sql = "UPDATE orders SET deleted = true, deleted_at = now() WHERE id = ?")
@Where(clause = "deleted = false")

Soft deletes with Hibernate in Spring

soft-delete jpa hibernate

Intermediate 9 steps

java

@GetMapping("/files/{id}")
public ResponseEntity<StreamingResponseBody> download(
        @PathVariable String id,
        @RequestHeader(value = HttpHeaders.RANGE, required = false) String rangeHeader) throws IOException {