Skip to main content

Kahn's Algorithm - Topological Sorting

Kahn's algorithm is a method used to perform a topological sort on a directed acyclic graph(DAG). A topological sort produces a linear ordering of vertices such that every directed edge from vertex u to vertex v, u comes before v in the ordering. Main applications of the algorithm are

  • Course prerequisite scheduling
  • Build dependency resolution
  • Task scheduling with dependencies
  • Detecting cycles in directed graph
FIG. TOPOLOGICAL SORTING● INTERACTIVE
Visualize
from collections import defaultdict, deque
 
 
class Graph:
def kahn_topological_sort(self, edges, num_vertices):
adj = defaultdict(list)
in_degree = defaultdict(int)
nodes = set()
 
# Build graph and in-degree map
for u, v in edges:
adj[u].append(v)
in_degree[v] += 1
nodes.add(u)
nodes.add(v)
 
# Initialize in-degree for all nodes (including isolated nodes)
for i in range(num_vertices):
in_degree.setdefault(i, 0)
nodes.add(i)
 
# Queue all nodes with in-degree 0
queue = deque([node for node in nodes if in_degree[node] == 0])
topo_order = []
 
while queue:
u = queue.popleft()
topo_order.append(u)
 
for v in adj[u]:
in_degree[v] -= 1
if in_degree[v] == 0:
queue.append(v)
 
if len(topo_order) != num_vertices:
raise ValueError("Graph has a cycle, topological sort not possible.")
 
return topo_order

Problems​

207. Course Schedule​

Medium·
Solutions:
FIG. COURSE SCHEDULE● INTERACTIVE
Visualize
from collections import defaultdict, deque
from typing import List
 
 
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
# Build adjacency list and in-degree map
adj = defaultdict(list)
in_degree = defaultdict(int)
 
# Initialize in-degree for all nodes
for node in range(numCourses):
in_degree[node] = 0
 
# Build graph from prerequisites
for course, prereq in prerequisites:
adj[prereq].append(course)
in_degree[course] += 1
 
# Queue all nodes with in-degree 0
queue = deque([node for node in range(numCourses) if in_degree[node] == 0])
processed_count = 0
 
while queue:
current = queue.popleft()
processed_count += 1
 
# Process all neighbors
for neighbor in adj[current]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
 
# Check if all courses can be finished (no cycle)
return processed_count == numCourses

802. Find Eventual Safe States​

Medium·
Solutions:
FIG. FIND EVENTUAL SAFE STATES● INTERACTIVE
Visualize
from collections import defaultdict, deque
from typing import List
 
 
class Solution:
def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
n = len(graph)
 
# Build reversed adjacency list and in-degree map
adj = defaultdict(list)
in_degree = defaultdict(int)
 
# Initialize in-degree for all nodes
for node in range(n):
in_degree[node] = 0
 
# Build reversed graph (reverse all edges)
for u in range(n):
for v in graph[u]:
adj[v].append(u) # Reverse: v -> u instead of u -> v
in_degree[u] += 1
 
# Queue all nodes with in-degree 0 (terminal nodes in original graph)
queue = deque([node for node in range(n) if in_degree[node] == 0])
safe_nodes = set()
 
while queue:
current = queue.popleft()
safe_nodes.add(current)
 
# Process all neighbors in reversed graph
for neighbor in adj[current]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
 
# Return safe nodes in sorted order
return sorted(list(safe_nodes))

1136. Parallel Courses​

Medium·
Solutions:
FIG. PARALLEL COURSES● INTERACTIVE
Visualize
class Solution:
def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:
adj = defaultdict(list)
in_degree = defaultdict(int)
nodes = set()
 
# Build graph and in-degree map
for u, v in relations:
adj[u].append(v)
in_degree[v] += 1
nodes.add(u)
nodes.add(v)
 
# Initialize in-degree for all nodes (including isolated nodes)
for i in range(1, n + 1):
in_degree.setdefault(i, 0)
nodes.add(i)
 
# Queue all nodes with in-degree 0
queue = deque([node for node in nodes if in_degree[node] == 0])
 
semesters = 0
totalProcessed = 0
 
while queue:
semesters += 1
m = len(queue)
totalProcessed += m
 
for _ in range(m):
u = queue.popleft()
 
for v in adj[u]:
in_degree[v] -= 1
if in_degree[v] == 0:
queue.append(v)
 
if totalProcessed != n:
return -1
 
return semesters

2115. Find All Possible Recipes from Given Supplies​

Medium·
Solutions:
FIG. FIND ALL POSSIBLE RECIPES FROM GIVEN SUP● INTERACTIVE
Visualize
from collections import defaultdict, deque
 
 
class Solution:
def findAllRecipes(
self,
recipes: list[str],
ingredients: list[list[str]],
supplies: list[str],
) -> list[str]:
# Build adjacency list and in-degree map
adj = defaultdict(list)
in_degree = defaultdict(int)
 
for recipe in recipes:
in_degree[recipe] = 0
 
# Convert supplies to set for O(1) lookup
available_supplies = set(supplies)
 
# Build dependency graph: ingredient -> recipes that need it
for recipe_idx, ingredient_list in enumerate(ingredients):
recipe = recipes[recipe_idx]
 
for ingredient in ingredient_list:
if ingredient not in available_supplies:
# ingredient -> recipe dependency
adj[ingredient].append(recipe)
in_degree[recipe] += 1
 
# Queue all recipes with in-degree 0 (can be made with available supplies/recipes)
queue = deque([recipe for recipe in recipes if in_degree[recipe] == 0])
 
created_recipes = []
 
while queue:
current_recipe = queue.popleft()
created_recipes.append(current_recipe)
 
# This recipe is now available, check dependent recipes
for dependent_recipe in adj[current_recipe]:
in_degree[dependent_recipe] -= 1
if in_degree[dependent_recipe] == 0:
queue.append(dependent_recipe)
 
return created_recipes