Graphs
Graph Patterns: Resolving Dependencies with Topological Sort
May 2026
7 min read
Whenever a problem explicitly states that Task A must be completed before Task B, it is an algorithmic cue to use Topological Sorting on a Directed Acyclic Graph (DAG).
Introduction
Dependency resolution is a fundamental concept in computer science, used heavily in build systems and package managers. In algorithmic logic, this is universally solved using Topological Sort.
Kahn's Algorithm
Kahn's Algorithm is the cleanest, most iterative way to implement a Topological Sort. It revolves around the concept of In-Degree—the number of prerequisites a node has.
- Graph Construction: Build the adjacency list and simultaneously calculate the in-degree for every node.
- Initialize Queue: Find all nodes with an in-degree of
0(tasks with no prerequisites) and push them into a queue. - Process and Reduce: Pop a node, add it to your result, and visit its neighbors. Reduce the neighbor's in-degree by
1. If a neighbor's in-degree hits0, it is now "unlocked" and can be pushed into the queue.
Always compare the size of your final sorted list to the total number of nodes. If they don't match, it proves that a circular dependency (deadlock) exists in the graph.
Implementation
java
class Solution {
public int[] topoSort(int V, ArrayList<ArrayList<Integer>> adj) {
int[] indegree = new int[V];
// Calculate incoming edges for every node
for (int i = 0; i < V; i++) {
for (int neighbor : adj.get(i)) {
indegree[neighbor]++;
}
}
Queue<Integer> q = new LinkedList<>();
// Push all independent nodes into the queue
for (int i = 0; i < V; i++) {
if (indegree[i] == 0) q.add(i);
}
int[] topo = new int[V];
int index = 0;
while (!q.isEmpty()) {
int node = q.poll();
topo[index++] = node;
for (int neighbor : adj.get(node)) {
indegree[neighbor]--;
if (indegree[neighbor] == 0) {
q.add(neighbor);
}
}
}
// If index != V, a cycle exists
return index == V ? topo : new int[0];
}
}