Introduction

In this section, we explore advanced variants of three fundamental graph algorithms — Topological Sort, Dijkstra’s Shortest Path, and Minimum Spanning Tree (MST). Each variant introduces new constraints or goals that frequently appear in FAANG-level interviews. We’ll highlight how the base algorithm’s template is modified and walk through example LeetCode problems (with solutions) for each variant. This will help solidify your understanding and prepare you for common interview questions.

Topological Sort

Topological sorting is used for ordering vertices of a Directed Acyclic Graph (DAG) based on dependencies. Interview questions often tweak the basic scenario (e.g. course prerequisite ordering) with additional requirements. Below are popular variants:

🔸 Course Schedule (Detecting Cycles in Prerequisites)

Modified Template: Determine if it’s possible to finish all courses given prerequisites (i.e., detect cycles). Uses Kahn’s algorithm (BFS with in-degrees). If all courses processed, no cycle; otherwise, a cycle exists.

Example Problem: LeetCode 207 – Medium. Given numCourses and prerequisites, return true if all courses can be finished, false otherwise.

Input/Output Example:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false (Cycle: 0 -> 1 -> 0)

How to Solve:

1. Model courses as graph nodes, prerequisites as directed edges.
2. Build adjacency list and compute in-degrees.
3. Initialize queue with all courses having in-degree 0.
4. Process queue: dequeue course, increment count of taken courses, decrement in-degree of neighbors. If neighbor's in-degree becomes 0, enqueue it.
5. Cycle detection: If queue empties before all courses taken (count < numCourses), a cycle exists.

Notes: DFS-based cycle detection is also an option.

🔸 Course Schedule II (Return Order of Courses)

Modified Template: Extends Course Schedule to return the actual topological order. Maintain a result list; append courses as they are dequeued. If cycle detected, return empty list.

Example Problem: LeetCode 210 – Medium. Return any valid course order, or empty array if impossible.

Input/Output Example:

Input: n = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,1,2,3] (or [0,2,1,3])

How to Solve:

Use Kahn’s BFS. When a course is dequeued, add it to the result list. If len(result) != n at the end, a cycle exists; return [].

Tips: Multiple valid orders may exist. BFS yields one such order.

🔸 Alien Dictionary (Ordering of Characters)

Modified Template: Nodes are characters. Edges derived by comparing adjacent words in a sorted alien dictionary. Graph construction is key. Handle invalid prefix cases (e.g., "abc" before "ab") and cycles.

Example Problem: LeetCode 269 – Hard. Given sorted alien words, output the alien alphabet order.

Input/Output Example:

Input: words = ["wrt","wrf","er","ett","rftt"]
Output: "wertf"

How to Solve:

1. Initialize graph: Add all unique characters from words as nodes.
2. Build edges: Compare adjacent words (word1, word2). First differing char c1 in word1 and c2 in word2 implies c1 -> c2. Handle invalid prefix: if word1 is prefix of word2 but len(word1) > len(word2) (e.g. "apple", "app"), it's invalid.
3. Topologically sort characters using Kahn's or DFS.
4. Cycle detection: If sort fails to include all characters, or a cycle is found, return "".

Notes: Common Google question. Handle edge cases like empty input, single characters.

Dijkstra’s Shortest Path Algorithm

Dijkstra’s finds shortest paths from a source in weighted graphs (non-negative weights). Variants add constraints or change optimization goals.

🔸 Network Delay Time (Single-Source Shortest Path)

Modified Template: Direct Dijkstra application. Output is max shortest time to any node. If any node unreachable, return -1.

Example Problem: LeetCode 743 – Medium. Given network nodes, travel times (edges), and start node K, find time for signal to reach all nodes.

Input/Output Example:

Input: times = [[2,1,1],[2,3,1],[3,4,1]], N = 4, K = 2
Output: 2

How to Solve:

Run Dijkstra from K. Result is max(dist_to_all_nodes). If any dist is infinity, return -1.

🔸 Cheapest Flights Within K Stops (Bounded Number of Edges)

Modified Template: Dijkstra state includes stops: (cost, city, stops_used). Prune paths exceeding K stops. Normal Dijkstra fails as shortest cost path might exceed K stops.

Example Problem: LeetCode 787 – Medium. Find cheapest price from src to dst with at most K stops.

Input/Output Example:

Input: n=3, flights=[[0,1,100],[1,2,100],[0,2,500]], src=0, dst=2, k=1
Output: 200 (path 0->1->2)

How to Solve:

Use min-heap with state (cost, city, stops). When expanding, if stops_used <= K, explore neighbors. Can also use Bellman-Ford variant.

🔸 Path with Maximum Probability

Modified Template: Maximize product of probabilities. Use max-heap with (probability, node). Edge relaxation becomes current_prob * edge_prob.

Example Problem: LeetCode 1514 – Medium. Find max probability path from start to end.

Input/Output Example:

Input: n=3, edges=[[0,1],[1,2],[0,2]], succProb=[0.5,0.5,0.2], start=0, end=2
Output: 0.25000 (path 0->1->2)

How to Solve:

Dijkstra with max-heap. Initialize maxProb[start]=1.0, others 0.0. Update maxProb[neighbor] if current_prob * edge_prob is greater.

🔸 The Maze II (Shortest Distance in a Maze)

Modified Template: Ball rolls until wall. Edge weight is distance rolled. Dijkstra on grid cells (distance, cell).

Example Problem: LeetCode 505 – Medium. Shortest distance for ball to stop at destination in maze.

Input/Output Example:

Input: maze = [[0,0,1,0,0]...], start = [0,4], destination = [4,4]
Output: 12

How to Solve:

Dijkstra on grid. From a cell, explore 4 directions: roll ball, calculate distance (steps) to wall/boundary. That's the edge weight.

Minimum Spanning Tree (MST)

MST algorithms (Kruskal's, Prim's) find min-weight edges to connect all vertices. Variants often involve graph construction or edge analysis.

🔸 Min Cost to Connect All Points (Spatial MST)

Modified Template: Points in a plane are vertices. Edge weight is Manhattan distance. Graph is complete. Use Prim's (add closest point to tree) or Kruskal's (generate all N^2 edges, sort).

Example Problem: LeetCode 1584 – Medium. Min cost to connect all 2D points using Manhattan distance.

Input/Output Example:

Input: points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
Output: 20

How to Solve:

Prim's: Start with a point, iteratively add nearest unvisited point. Kruskal's: Calculate all N*(N-1)/2 edge weights (distances), sort, use Union-Find.

🔸 Optimize Water Distribution in a Village

Modified Template: Combine well costs and pipe costs. Add virtual source node. Edges from source to houses = well costs. Edges between houses = pipe costs. Find MST on this augmented graph.

Example Problem: LeetCode 1168 – Hard. Min cost to supply water to all houses (build wells or use pipes).

Input/Output Example:

Input: n=3, wells=[1,2,2], pipes=[[1,2,1],[2,3,1]]
Output: 3 (Well at house1, pipe 1-2, pipe 2-3)

How to Solve:

Create graph with N+1 nodes (N houses + 1 virtual source). Edges: (source, house_i) with weight wells[i], and (house_u, house_v) with pipe_cost. Run MST (Kruskal's or Prim's).

🔸 Critical and Pseudo-Critical Edges in MST

Modified Template: Analyze each edge's role. Critical: in every MST (removing it increases MST cost). Pseudo-critical: in some MSTs but not all.

Example Problem: LeetCode 1489 – Hard. Find critical and pseudo-critical edges.

Input/Output Example:

Input: n=5, edges=[[0,1,1],[1,2,1],[2,3,2],...]
Output: [[0,1],[2,3,4,5]] (Indices of critical, then pseudo-critical)

How to Solve:

1. Find original MST weight (W).
2. For each edge:
   • Test criticality: Remove edge, find MST. If cost > W or disconnected, it's critical.
   • Test pseudo-criticality (if not critical): Force edge in, find MST. If cost == W, it's pseudo-critical.

Interactive Animation (Topological Sort - Course Schedule)

The animation below demonstrates Topological Sort using Kahn's Algorithm for the "Course Schedule" problem. Example: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]. This means 0 is a prerequisite for 1 and 2; 1 and 2 are prerequisites for 3. Watch how courses with no pending prerequisites are processed.