Tree & GraphAdvanced
Topological Sort
Order vertices of a directed acyclic graph (DAG) so every edge goes from earlier to later in the ordering.
Course Prerequisites Graph
6 courses with prerequisites. Course i requires courses in prereqs[i].
Prerequisites: 0<-[4,5], 1<-[3,4], 2<-[5], 3<-[2]
Step 1/8
Speed:
When to Use
- Task scheduling with dependencies
- Course prerequisites
- Build order
- Detect cycles in directed graph
Key Indicators
- Dependencies/prerequisites
- Ordering with constraints
- DAG (directed acyclic graph)
- Build/task order
Complexity
Time
O(V + E)
Space
O(V)
Common Problems
Course ScheduleCourse Schedule IIAlien DictionaryMinimum Height Trees
Code
indegree = count incoming edges
queue = [nodes with 0 indegree]
order = []
while queue:
node = queue.pop(0)
order.append(node)
for neighbor in node.neighbors:
indegree[neighbor] -= 1
if indegree[neighbor] == 0:
queue.append(neighbor)Want all 29 patterns with detailed visual walkthroughs?
The complete book includes 84 practice problems, full decision tree, and illustrated step-by-step solutions.
Book Coming Soon ($4.99)