Algorithm1 Practice2 Interview

Kahn's Algorithm

GuideCode Labs

Produce a topological order by repeatedly removing zero-indegree vertices with a queue. Learn the algorithm's preconditions, state transition, correctness argument, Python cost model, and transfer from one focused drill to a full Interview Problem.

Recognize it when

Consider Kahn's Algorithm when the prompt's constraints and required operations match this shape: Produce a topological order by repeatedly removing zero-indegree vertices with a queue.

On this page · Count Every Incoming Edge

Checking your account…

Count Every Incoming Edge

Kahn’s algorithm starts by computing indegree for every node from every directed edge. Indegree represents unresolved prerequisites, including duplicate edges if the input permits them.

Seed All Zero Indegree Nodes

Every node with zero unresolved prerequisites is ready. Seeding all of them is required to cover disconnected DAG components and isolated vertices.

Trace Kahn Indegree Updates

Reference

import heapq

def kahn_trace(node_count,edges):
    adjacency=[[] for _ in range(node_count)];indegree=[0]*node_count
    for source,target in edges:adjacency[source].append(target);indegree[target]+=1
    ready=[n for n in range(node_count) if indegree[n]==0];heapq.heapify(ready);trace=[]
    while ready:
        node=heapq.heappop(ready)
        for neighbor in adjacency[node]:
            indegree[neighbor]-=1
            if indegree[neighbor]==0:heapq.heappush(ready,neighbor)
        trace.append([node,indegree.copy(),sorted(ready)])
    return trace

Practice

Implement kahn_trace(node_count,edges). Return [removed,indegree,ready] after each queue removal using ascending ready order.

def kahn_trace(node_count,edges):
    pass

Public tests

Remove outgoing edges once

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Remove Edges as Nodes Leave

When a ready node is processed, decrement each outgoing neighbor once. Enqueue a neighbor exactly when its indegree becomes zero, never before and never repeatedly.

Order Nodes with Kahn Algorithm

Reference

from collections import deque

def kahn_order(node_count,edges):
    adjacency=[[] for _ in range(node_count)];indegree=[0]*node_count
    for source,target in edges:adjacency[source].append(target);indegree[target]+=1
    queue=deque(node for node in range(node_count) if indegree[node]==0);order=[]
    while queue:
        node=queue.popleft();order.append(node)
        for neighbor in adjacency[node]:
            indegree[neighbor]-=1
            if indegree[neighbor]==0:queue.append(neighbor)
    return order if len(order)==node_count else []

Practice

Implement kahn_order(node_count,edges). Return ascending-ready order or [] if a cycle prevents processing all nodes.

def kahn_order(node_count,edges):
    pass

Public tests

Detect unprocessed cyclic nodes

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Use Processed Count to Detect Cycles

If the queue empties before V nodes are processed, the remaining subgraph has no zero-indegree node and therefore contains a directed cycle. The algorithm takes O(V + E) time and space.

Explain It in an Interview

Say: “Indegree counts unresolved prerequisites. Zero-indegree nodes are safe next choices; removing one resolves each outgoing prerequisite. If processed count is short, a cycle blocked the rest.” State how ready-node ordering affects deterministic output.

Python Version Note

Python 3.11+

The code uses standard Python syntax and containers supported by the browser Judge. The Kahn's Algorithm proof does not depend on a minor Python release.

Verify in Python docs

Complexity & Invariants

Interview bounds depend on the stated representation, input model, and real Python operations.

Operation	Average	Worst	Interview note
Kahn's Algorithm complete workflow	`O(V log V + E)`	`O(V log V + E)`	Dependency graphs expose currently available work as the nodes with zero remaining incoming edges. A node enters a frontier exactly when all of its predecessors have been removed, and each edge decrements indegree once.

Space

O(V + E) for the focused Maintain an Indegree Frontier implementation.

Assumptions

Zero-indegree nodes form the available layer, and removing them updates each outgoing dependency exactly once. If every node is emitted the layers respect all edges; otherwise the remaining positive indegrees certify a directed cycle.
The bound counts Python sorting, slicing, hashing, heap, recursion, and container-copy costs rather than treating syntax as free.

Invariants Worth Saying Aloud

State the precise Kahn's Algorithm invariant before coding and preserve it after every update, traversal step, or recursive return.
Each stored indegree equals the number of unmet incoming dependencies.
The queue contains exactly discovered vertices with zero unmet dependencies.
Dependency graphs expose currently available work as the nodes with zero remaining incoming edges. Preserve this claim after every transition.
A node enters a frontier exactly when all of its predecessors have been removed, and each edge decrements indegree once. Preserve this claim after every transition.

When To Use Or Avoid Kahn's Algorithm

Use It When

Use Kahn's Algorithm when this precondition is stated or can be proved: Dependencies form a directed graph, and a complete ordering exists only when the graph is acyclic.
Use it when this maintained state removes repeated work: Each stored indegree equals the number of unmet incoming dependencies.

Choose Another Tool When

Avoid Kahn's Algorithm when this precondition is absent: Dependencies form a directed graph, and a complete ordering exists only when the graph is acyclic.
Avoid it when a simpler direct scan satisfies the constraints with less implementation risk.

Common Pitfalls

These are the mistakes most likely to survive a happy-path example and fail a boundary case.

Applying the algorithm without its precondition

Verify algorithm preconditions such as sorted input, nonnegative weights, acyclicity, or admissible heuristics before applying it.

Prevent it: State and verify this precondition before coding: Dependencies form a directed graph, and a complete ordering exists only when the graph is acyclic.

Avoid

def kahn_frontier_layers(node_count, edges):
    pass

Use instead

def kahn_frontier_layers(node_count, edges):
    graph = [[] for _ in range(node_count)]
    indegree = [0] * node_count
    for before, after in edges:
        graph[before].append(after)
        indegree[after] += 1
    frontier = [node for node, degree in enumerate(indegree) if degree == 0]
    layers = []
    processed = 0
    while frontier:
        frontier.sort()
        layers.append(frontier)
        next_frontier = []
        for node in frontier:
            processed += 1
            for neighbor in graph[node]:
                indegree[neighbor] -= 1
                if indegree[neighbor] == 0:
                    next_frontier.append(neighbor)
        frontier = next_frontier
    return layers if processed == node_count else []

Where you will hit this: Maintain an Indegree Frontier(opens in a new tab)

Breaking the state transition

Returns partial layers without verifying that every node was processed, so directed cycles are accepted.

Prevent it: Preserve this proof obligation: Only zero-indegree vertices are emitted, so every prerequisite precedes each dependent; a short result reveals a cycle.

Avoid

def kahn_frontier_layers(node_count, edges):
    graph = [[] for _ in range(node_count)]
    indegree = [0] * node_count
    for before, after in edges:
        graph[before].append(after); indegree[after] += 1
    frontier = [i for i, degree in enumerate(indegree) if degree == 0]
    layers = []
    while frontier:
        layers.append(sorted(frontier)); next_frontier = []
        for node in frontier:
            for neighbor in graph[node]:
                indegree[neighbor] -= 1
                if indegree[neighbor] == 0: next_frontier.append(neighbor)
        frontier = next_frontier
    return layers

Use instead

def kahn_frontier_layers(node_count, edges):
    graph = [[] for _ in range(node_count)]
    indegree = [0] * node_count
    for before, after in edges:
        graph[before].append(after)
        indegree[after] += 1
    frontier = [node for node, degree in enumerate(indegree) if degree == 0]
    layers = []
    processed = 0
    while frontier:
        frontier.sort()
        layers.append(frontier)
        next_frontier = []
        for node in frontier:
            processed += 1
            for neighbor in graph[node]:
                indegree[neighbor] -= 1
                if indegree[neighbor] == 0:
                    next_frontier.append(neighbor)
        frontier = next_frontier
    return layers if processed == node_count else []

Where you will hit this: Maintain an Indegree Frontier(opens in a new tab)

Hiding Python work in the claimed bound

Include visited state, boundary cases, recursion depth, and hidden copying costs in correctness and complexity analysis.

Prevent it: Count every sort, slice, copy, membership check, heap update, and recursive frame before claiming O(V log V + E).

Avoid

def kahn_frontier_layers(node_count, edges):
    graph = [[] for _ in range(node_count)]
    indegree = [0] * node_count
    for before, after in edges:
        graph[before].append(after); indegree[after] += 1
    frontier = [i for i, degree in enumerate(indegree) if degree == 0]
    layers = []
    while frontier:
        layers.append(sorted(frontier)); next_frontier = []
        for node in frontier:
            for neighbor in graph[node]:
                indegree[neighbor] -= 1
                if indegree[neighbor] == 0: next_frontier.append(neighbor)
        frontier = next_frontier
    return layers

Use instead

def kahn_frontier_layers(node_count, edges):
    graph = [[] for _ in range(node_count)]
    indegree = [0] * node_count
    for before, after in edges:
        graph[before].append(after)
        indegree[after] += 1
    frontier = [node for node, degree in enumerate(indegree) if degree == 0]
    layers = []
    processed = 0
    while frontier:
        frontier.sort()
        layers.append(frontier)
        next_frontier = []
        for node in frontier:
            processed += 1
            for neighbor in graph[node]:
                indegree[neighbor] -= 1
                if indegree[neighbor] == 0:
                    next_frontier.append(neighbor)
        frontier = next_frontier
    return layers if processed == node_count else []

Where you will hit this: Course Schedule(opens in a new tab)

Reviewed References

Official Python documentation supports language behavior. Canonical problem pages provide additional practice context.

Python collections.deque(opens in a new tab)
python-docs · checked 2026-07-12
Python deque Recipes(opens in a new tab)
python-docs · checked 2026-07-27

Checking your account…

Kahn's Algorithm Code Labs

Count Every Incoming Edge

Seed All Zero Indegree Nodes

Public tests

Remove Edges as Nodes Leave

Public tests

Use Processed Count to Detect Cycles

Explain It in an Interview

Python Version Note

Complexity & Invariants

Space

Assumptions

Invariants Worth Saying Aloud

When To Use Or Avoid Kahn's Algorithm

Use It When

Choose Another Tool When

Common Pitfalls

Applying the algorithm without its precondition

Breaking the state transition

Hiding Python work in the claimed bound

Related Practice

Related Interview Problems

Reviewed References