Kahn's Algorithm - Topological Sorting

A topological sort lays every vertex of a directed acyclic graph (DAG) out in a line such that every edge points forward - for every edge u → v, u appears before v. Kahn's algorithm builds that line by repeatedly placing whichever vertices have no remaining prerequisites (in-degree 0).

Why the order is a lineup and not a walk, why the cycle test is len(order) == n rather than "the pool started empty," and what the pool's container choice does and does not affect are all on Cycles & Ordering. Step through it here:

FIG. TOPOLOGICAL SORTING● INTERACTIVE

visualization loads as you reach it

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·

207Course Schedule

1

Kahn's Algorithm

O(2(V + E))

O(V + E)

FIG. COURSE SCHEDULE● INTERACTIVE

visualization loads as you reach it

Time

O(2(V + E))

• Building adj and in_degree costs O(V + E), where V = numCourses and E = len(prerequisites).
• The BFS then dequeues each of the V nodes once and scans each of the E edges once more - a second, distinct O(V + E) pass, 2(V + E).

Space

O(V + E)

• adj stores V keys and E total edge entries, in_degree holds V entries, and queue holds up to V nodes.

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·

802Find Eventual Safe States

1

Kahn's Algorithm

O(2(V + E) + V log V)

O(sort + V + E)

FIG. FIND EVENTUAL SAFE STATES● INTERACTIVE

visualization loads as you reach it

Time

O(2(V + E) + V log V)

• V is len(graph) (number of nodes), E is the total number of edges across graph.
• Building the reversed adj list and in_degree map walks every node and every edge once - O(V + E).
• The while queue loop (Kahn's algorithm) visits every node and every reversed edge once more - another O(V + E) - together 2(V + E).
• sorted(list(safe_nodes)) sorts up to V nodes at the end - O(V log V).

Space

O(sort + V + E)

• adj stores every reversed edge, O(E).
• in_degree, queue, and safe_nodes each hold at most V nodes.
• Sorting algorithms are typically O(log n) space (in-place, recursion stack only), but Python's list.sort() is Timsort, which allocates up to O(n) auxiliary space in the worst case - that's what sort stands for here.

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·

1136Parallel Courses

1

Kahn's Algorithm

O(3n + 2e)

O(3n + e)

FIG. PARALLEL COURSES● INTERACTIVE

visualization loads as you reach it

Time

O(3n + 2e)

• n is the number of courses, e is len(relations).
• Building adj/in_degree/nodes from relations is one O(e) pass.
• Filling in isolated courses (for i in range(1, n + 1)) is one O(n) pass.
• Building the initial queue from nodes is another O(n) pass.
• The BFS pops each course at most once (O(n)) and relaxes each edge in adj[u] at most once across the whole run (O(e)).
• Node-sized passes: n (fill isolated) + n (build queue) + n (BFS pops) = 3n. Edge-sized passes: e (build) + e (relax) = 2e.

Space

O(3n + e)

• adj stores each of the e edges once across its lists - O(e).
• in_degree, nodes, and queue each hold up to n courses - three separate O(n) allocations, 3n.

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·

2115Find All Possible Recipes from Given Supplies

1

Kahn'a Algorithm

O(R + m + S)

O(R + m + S)

FIG. FIND ALL POSSIBLE RECIPES FROM GIVEN SUP● INTERACTIVE

visualization loads as you reach it

Time

O(R + m + S)

• R is the number of recipes, m is the total number of ingredient entries across all ingredients lists, and S is the number of supplies.
• Building available_supplies from supplies is O(S).
• The nested loop over recipes/ingredients builds adj and in_degree in O(m).
• Kahn's BFS pops each of the R recipes once and walks each of the m adjacency edges once - O(R + m).

Space

O(R + m + S)

• adj holds up to m entries, in_degree holds R entries, and available_supplies holds S entries.
• queue and created_recipes each hold up to R recipes.

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

---