03
Topological Sort Visualizer
Chapter 3 • Intermediate
90 min
Topological Sort Visualizer
What is Topological Sort?
A topological sort is a linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every directed edge (u, v), vertex u comes before v in the ordering.
Key Properties
- Only possible for DAGs (no cycles)
- Not unique: Multiple valid orderings may exist
- Represents a valid sequence of dependencies
Applications
- Course prerequisites: Order courses to satisfy prerequisites
- Build systems: Compile dependencies in correct order
- Task scheduling: Execute tasks respecting dependencies
- Event ordering: Determine chronological order of events
Algorithm 1: Kahn's Algorithm (BFS-based)
Steps
- Calculate in-degree of all vertices
- Add all vertices with in-degree 0 to queue
- While queue is not empty:
- Remove vertex u from queue
- Add u to result
- For each neighbor v of u:
- Decrease in-degree of v
- If in-degree becomes 0, add v to queue
- If result contains all vertices, return result
- Otherwise, graph has cycle
Implementation
python.js
from collections import deque
def topological_sort_kahn(graph):
"""
Topological sort using Kahn's algorithm.
Time: O(V + E), Space: O(V)
"""
n = len(graph)
in_degree = [0] * n
# Calculate in-degrees
for u in range(n):
for v in graph[u]:
in_degree[v] += 1
# Queue for vertices with in-degree 0
queue = deque()
for i in range(n):
if in_degree[i] == 0:
queue.append(i)
result = []
while queue:
u = queue.popleft()
result.append(u)
# Remove u and update in-degrees
for v in graph[u]:
in_degree[v] -= 1
if in_degree[v] == 0:
queue.append(v)
# Check for cycle
if len(result) != n:
return None # Cycle exists
return result
Algorithm 2: DFS-based
Steps
- For each unvisited vertex:
- Mark as visiting
- Recursively visit all neighbors
- Mark as visited and add to result
- Reverse result to get topological order
Implementation
python.js
def topological_sort_dfs(graph):
"""
Topological sort using DFS.
Time: O(V + E), Space: O(V)
"""
n = len(graph)
visited = [False] * n
result = []
def dfs(u):
visited[u] = True
for v in graph[u]:
if not visited[v]:
dfs(v)
result.append(u)
for i in range(n):
if not visited[i]:
dfs(i)
return result[::-1] # Reverse to get correct order
Cycle Detection
Topological sort can detect cycles: if not all vertices are included in result, cycle exists.
python.js
def has_cycle_topological(graph):
"""Detect cycle using topological sort"""
n = len(graph)
in_degree = [0] * n
for u in range(n):
for v in graph[u]:
in_degree[v] += 1
queue = deque()
for i in range(n):
if in_degree[i] == 0:
queue.append(i)
count = 0
while queue:
u = queue.popleft()
count += 1
for v in graph[u]:
in_degree[v] -= 1
if in_degree[v] == 0:
queue.append(v)
return count != n # Cycle exists if count < n
Example: Course Prerequisites
python.js
# Courses: 0=Math, 1=Physics, 2=Chemistry, 3=CS, 4=Algorithms
# Prerequisites: Math → Physics, Math → Chemistry, Physics → CS, CS → Algorithms
graph = [
[1, 2], # Math → Physics, Chemistry
[3], # Physics → CS
[], # Chemistry
[4], # CS → Algorithms
[] # Algorithms
]
order = topological_sort_kahn(graph)
# Result: [0, 1, 2, 3, 4] or [0, 2, 1, 3, 4]
# Valid order: Math → (Physics, Chemistry) → CS → Algorithms
All Topological Orderings
To find all possible topological orderings:
python.js
def all_topological_sorts(graph):
"""Find all possible topological orderings"""
n = len(graph)
in_degree = [0] * n
for u in range(n):
for v in graph[u]:
in_degree[v] += 1
visited = [False] * n
result = []
all_results = []
def backtrack():
# Check if all vertices are processed
flag = False
for i in range(n):
if in_degree[i] == 0 and not visited[i]:
# Include vertex in result
visited[i] = True
result.append(i)
# Reduce in-degree of neighbors
for v in graph[i]:
in_degree[v] -= 1
# Recurse
backtrack()
# Backtrack
visited[i] = False
result.pop()
for v in graph[i]:
in_degree[v] += 1
flag = True
if not flag:
all_results.append(result[:])
backtrack()
return all_results
Practice Problems
- Implement both topological sort algorithms
- Find valid course schedule given prerequisites
- Detect cycles in directed graph
- Find all topological orderings
- Longest path in DAG using topological sort
- Critical path in project scheduling