Topological Sort

Use Cases

Use Case	Description	Example
Topological Sorting of a Directed Acyclic Graph (DAG)	Given a directed acyclic graph, return a linear ordering of its vertices such that for every directed edge u to v , vertex u comes before vertex v.	For the graph with edges: A → B, A → C, B → D, C → D, one possible result is [A, B, C, D].
Course Scheduling	Given a list of courses and their prerequisites, determine an order to take the courses.	For courses: `{0: [], 1: [0], 2: [1]}`, a valid order could be [0, 1, 2].

Code Template

Initialization

indegree = defaultdict(int): Store the indegree (number of incoming edges) for each node in the graph. It initializes the count to zero for any node that hasn't been encountered yet.
queue = deque([node for node in graph if indegree[node] == 0]): A deque (double-ended queue) is initialized with nodes that have an indegree of zero. These are the starting points for the topological sort, as they don't have any prerequisites.

Calculate node indegree

The outer loop goes through each node in the graph. The inner loop processes each nei of the current node.
The indegree of each nei is incremented by 1, counting how many edges point to it.

Processes node

while queue: This loop continues as long as there are nodes in the queue. The queue contains nodes that are ready to be processed (i.e., they have zero indegree).
node = queue.popleft(): The popleft() method removes and returns the first node from the queue. This node is the next one to be processed in the topological order.

Updating indegrees

for nei in graph[node]: This loop goes through each nei of the current node. These are the nodes that are directly reachable from node.
indegree[nei] -= 1: The indegree of the nei is decreased by 1. This reflects that one incoming edge (from node to nei) has been processed.
if indegree[nei] == 0: After decrementing, Checks if the nei now has an indegree of zero. This means there are no remaining incoming edges to this node.
queue.append(nei): If the indegree is zero, the nei is added to the queue, making it ready to be processed in subsequent iterations.

def topological_sort(graph):
    queue = deque([node for node in graph if indegree[node] == 0])
    result = []
    indegree = defaultdict(int)

Common mistakes

Wrong Cycle Detection

# Wrong: missing cycle detection
return result  # Always returns result without checking for cycles
# Correct:
if len(result) != len(graph):  # Check if all nodes are visited
    return []  # or raise exception for cycle detection
return result

Wrong Queue Operation

# Wrong: using pop() instead of popleft()
node = queue.pop()  # Gets last element instead of first
# Wrong: using append_left instead of append
queue.appendleft(nei)  # Adds to wrong end
# Correct:
node = queue.popleft()
queue.append(nei)

Issues and consideration

Ensure that the input graph is a valid directed acyclic graph (DAG). Topological sorting is only applicable to DAGs.
If the graph has cycles, the algorithm will not produce a valid topological sort. You might want to check if the length of the result is equal to the number of nodes in the graph after processing. If not, it indicates a cycle.

210. Course Schedule II

class Solution:
    def findOrder(self, numCourses, prerequisites):
        # Step 1: Build the graph and indegree array
        graph = defaultdict(list)
        indegree = [0] * numCourses
        
        for ai, bi in prerequisites:
            graph[bi].append(ai)  # bi -> ai
            indegree[ai] += 1      # Increase indegree for ai
        
        # Step 2: Initialize the queue with all courses having no prerequisites
        queue = deque([i for i in range(numCourses) if indegree[i] == 0])
        result = []
        
        # Step 3: Process the courses
        while queue:
            node = queue.popleft()
            result.append(node)
            for nei in graph[node]:
                indegree[nei] -= 1
                if indegree[nei] == 0:
                    queue.append(nei)
        
        # Step 4: Check if we were able to schedule all courses
        if len(result) == numCourses:
            return result
        else:
            return []  # Cycle detected or not all courses can be completed

444. Sequence Reconstruction

class Solution:
    def sequenceReconstruction(self, org: List[int], seqs: List[List[int]]) -> bool:
        graph = defaultdict(set)
        indegree = defaultdict(int)
        
        nodes = set()
        for seq in seqs:
            nodes.update(seq)
            
        if set(org) != nodes:
            return False
            
        # Build graph from sequences
        for seq in seqs:
            for i in range(len(seq) - 1):
                if seq[i+1] not in graph[seq[i]]:
                    graph[seq[i]].add(seq[i+1])
                    indegree[seq[i+1]] += 1
        
        queue = deque([x for x in org if indegree[x] == 0])
        result = []
        
        while queue:
            if len(queue) > 1:
                return False
            
            node = queue.popleft()
            result.append(node)
            
            for nei in graph[node]:
                indegree[nei] -= 1
                if indegree[nei] == 0:
                    queue.append(nei)
        return result == org

1136. Parallel Courses

class Solution:
    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:
        graph = defaultdict(list)
        indegree = [0] * (n + 1)
        
        # Build graph
        for prev, next in relations:
            graph[prev].append(next)
            indegree[next] += 1
        
        queue = deque([i for i in range(1, n + 1) if indegree[i] == 0])
        semester = 0
        count = 0
        
        while queue:
            semester += 1
            size = len(queue)
            
            for _ in range(size):
                node = queue.popleft()
                count += 1
                for nei in graph[node]:
                    indegree[nei] -= 1
                    if indegree[nei] == 0:
                        queue.append(nei)
        return semester if count == n else -1

Topological Sort

Use Cases

Code Template

Initialization

Calculate node indegree

Processes node

Updating indegrees

Common mistakes

Issues and consideration

Related Problem