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

Python

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

210. Course Schedule IIMedium

207. Course Schedule

Kahn's Algorithm

Interactive Visualization

Python

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

802. Find Eventual Safe States

Kahn's Algorithm

Interactive Visualization

Python

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

1136. Parallel Courses

Kahn's Algorithm

Interactive Visualization

Python

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

2115. Find All Possible Recipes from Given Supplies

Kahn'a Algorithm

Interactive Visualization

Python

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

---