Graphs Advanced

1 / 5

Topological Sort (Kahn)

  • Compute in-degrees
  • Queue nodes with in-degree 0
  • Pop → output → decrement neighbors
  • If output size < n → cycle
2 / 5

Course Schedule vs Course Order

  • Schedule = “Is there a cycle?”
  • Order = “Return any valid ordering”
  • Same algorithm, different output
3 / 5

Dijkstra’s Algorithm

  • Min-heap of (dist, node)
  • Pop smallest, relax edges
  • Positive weights only
  • Ignore stale heap entries
4 / 5

Takeaway

  • Ordering problems = DAG reasoning
  • Shortest path = greedy frontier with heap
5 / 5
Use arrow keys or click edges to navigate. Press H to toggle help, F for fullscreen.