Advanced Graphs

Beyond basic traversal, some graph problems need ordering constraints (topological sort) or weighted shortest paths (Dijkstra, Bellman-Ford, minimum spanning trees).

Key concepts

• Topological sort: an ordering of nodes in a directed acyclic graph where every edge points forward — used for "must happen before" dependency problems.
• Dijkstra's algorithm: finds shortest paths from a source in a weighted graph with non-negative edges, using a min-heap.
• Cycle detection in directed graphs: if a topological sort can't include every node, a cycle exists.

When to use it

• The problem has ordering or prerequisite constraints ("do X before Y").
• Edges have weights or costs and you need the cheapest path, not just any path.

Tips

• Topological sort via BFS (tracking in-degrees) is usually easier to implement correctly than the DFS version.
• If a topological sort can't place every node, the graph has a cycle — that's a reliable validity check.
• A min-heap keyed by current shortest distance is the core of Dijkstra's algorithm — it's BFS with weights.

Practice problems (6)

Blind 75 (1):

• Alien Dictionary Hard — Read & practice · LeetCode ↗

More from Blind 150 (5):

• Reconstruct Itinerary Hard — Read & practice · LeetCode ↗
• Min Cost to Connect All Points Medium — Read & practice · LeetCode ↗
• Network Delay Time Medium — Read & practice · LeetCode ↗
• Swim In Rising Water Hard — Read & practice · LeetCode ↗
• Cheapest Flights Within K Stops Medium — Read & practice · LeetCode ↗