Graphs Advanced

Why this module exists

You already know DFS/BFS for traversal. Advanced graph interviews usually pivot to ordering and optimal paths. This module focuses on:

1. Topological sorting — ordering tasks with prerequisites
2. Cycle detection — proving an ordering is impossible
3. Shortest paths with weights — Dijkstra’s greedy frontier

Mastering these gives you a toolkit for scheduling, dependency management, and network routing problems.

1) Topological Sort (Kahn’s Algorithm)

If edges mean “must come before,” then a valid order is a topological ordering.

Kahn’s algorithm (BFS on in-degrees):

1. Count in-degrees for every node.
2. Push all nodes with in-degree 0 into a queue.
3. Pop, append to order, and reduce neighbors’ in-degree.
4. If you processed all nodes, you have an ordering.

Invariant: Nodes in the queue have no remaining prerequisites.

Cycle detection: If you can’t process all nodes, a cycle exists.

2) Course Schedule vs Course Order

• Course Schedule asks: “Does an order exist?”
• Course Order asks: “Return any valid order.”

Same algorithm, different output:

• Schedule returns visited == n.
• Order returns the list if len(order) == n, otherwise [].

3) Dijkstra’s Algorithm (Shortest Paths)

When edges have positive weights, greedy works:

1. Start from the source.
2. Always expand the closest unvisited node.
3. Relax edges to improve distances.

Key idea: once a node is popped from the min-heap, its distance is final.

Common traps:

• Negative weights break the greedy property.
• Use a min-heap and ignore stale entries.

Interview signals

• You can model real systems (dependencies, pipelines, build graphs).
• You can reason about constraints (cycles make an order impossible).
• You can justify greedy correctness (Dijkstra).

Problems in this module

• Course Schedule — detect cycles in prerequisites
• Course Order — produce a valid topological ordering
• Dijkstra Shortest Path — shortest distances in weighted graphs