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
Interactive Visualization
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
Medium1 solution1 playground
207. Course Schedule
Solutions:
Interactive Visualization
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
Medium1 solution1 playground
802. Find Eventual Safe States
Solutions:
Interactive Visualization
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))
Medium1 solution1 playground
1136. Parallel Courses
Solutions:
Interactive Visualization
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
Medium1 solution1 playground
2115. Find All Possible Recipes from Given Supplies
Solutions:
Interactive Visualization
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