Solution: Kahn's Algorithm (BFS)
from collections import deque, defaultdict
def topological_sort_kahn(num_nodes, edges):
"""
Kahn's algorithm for topological sort
Args:
num_nodes: Number of nodes (0 to num_nodes-1)
edges: List of [from, to] directed edges
Returns:
List of nodes in topological order, or [] if cycle exists
Time: O(V + E)
Space: O(V + E)
"""
# Build adjacency list and in-degree count
graph = defaultdict(list)
in_degree = [0] * num_nodes
for src, dst in edges:
graph[src].append(dst)
in_degree[dst] += 1
# Start with nodes having no incoming edges
queue = deque([i for i in range(num_nodes) if in_degree[i] == 0])
result = []
while queue:
node = queue.popleft()
result.append(node)
# Remove this node and its edges
for neighbor in graph[node]:
in_degree[neighbor] -= 1
# If neighbor now has no incoming edges, add to queue
if in_degree[neighbor] == 0:
queue.append(neighbor)
# If we processed all nodes, no cycle exists
if len(result) == num_nodes:
return result
else:
return [] # Cycle detected
# Example: Course Schedule
def can_finish(num_courses, prerequisites):
"""
LeetCode 207: Course Schedule
Can you finish all courses given prerequisites?
"""
result = topological_sort_kahn(num_courses, prerequisites)
return len(result) == num_courses
# Test
print(can_finish(2, [[1,0]])) # True: can take 0 then 1
print(can_finish(2, [[1,0],[0,1]])) # False: cycle!
Solution: DFS-based Approach
def topological_sort_dfs(num_nodes, edges):
"""
DFS-based topological sort with cycle detection
Time: O(V + E)
Space: O(V + E)
"""
graph = defaultdict(list)
for src, dst in edges:
graph[src].append(dst)
# 0: white (unvisited), 1: gray (processing), 2: black (done)
state = [0] * num_nodes
result = []
has_cycle = False
def dfs(node):
nonlocal has_cycle
if state[node] == 1: # Gray: found cycle
has_cycle = True
return
if state[node] == 2: # Black: already processed
return
state[node] = 1 # Mark as processing (gray)
for neighbor in graph[node]:
dfs(neighbor)
if has_cycle:
return
state[node] = 2 # Mark as done (black)
result.append(node) # Add in post-order
# Visit all nodes
for i in range(num_nodes):
if state[i] == 0:
dfs(i)
if has_cycle:
return []
return result[::-1] # Reverse for correct order
# Test
print(topological_sort_dfs(4, [[0,1],[1,2],[2,3]])) # [0,1,2,3]
print(topological_sort_dfs(3, [[0,1],[1,2],[2,0]])) # [] (cycle)
Complete Example: Course Schedule II
def find_order(num_courses, prerequisites):
"""
LeetCode 210: Course Schedule II
Return valid course ordering or [] if impossible
Example:
Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,2,1,3] or [0,1,2,3]
Explanation: Take course 0, then 2, then 1, then 3
"""
graph = defaultdict(list)
in_degree = [0] * num_courses
for course, prereq in prerequisites:
graph[prereq].append(course)
in_degree[course] += 1
queue = deque([i for i in range(num_courses) if in_degree[i] == 0])
order = []
while queue:
course = queue.popleft()
order.append(course)
for next_course in graph[course]:
in_degree[next_course] -= 1
if in_degree[next_course] == 0:
queue.append(next_course)
return order if len(order) == num_courses else []
# Test
print(find_order(4, [[1,0],[2,0],[3,1],[3,2]]))
# Output: [0, 1, 2, 3] or [0, 2, 1, 3]
Complexity Analysis
Kahn's Algorithm:
- Time Complexity: O(V + E) - visit each vertex once, process each edge once
- Space Complexity: O(V + E) - adjacency list + in-degree array + queue
- Best for: When you need to track in-degrees or process layer by layer
DFS-based:
- Time Complexity: O(V + E) - same as Kahn's
- Space Complexity: O(V + E) - adjacency list + recursion stack
- Best for: When graph structure favors DFS or detecting cycles
Common Pitfalls
- Forgetting to check for cycles (infinite loop possibility)
- Not handling disconnected components
- Assuming unique topological ordering (multiple valid orders exist)
- Using on cyclic graphs (will fail)
- Not reversing result in DFS approach
Related Problems
