Advanced Graphs

6 questions, each a named algorithm. The work is recognising which one applies — and, in two cases, noticing that the obvious choice is wrong.

The algorithms

Algorithm	Solves	Question
Hierholzer's	Eulerian path — use every edge once	1
Prim's / Kruskal's	minimum spanning tree	2
Dijkstra	shortest path, non-negative weights	3, 4
Topological sort	ordering from constraints	5
Bellman-Ford	shortest path with a hop limit	6

Weighted edges break BFS

BFS orders by hop count; Dijkstra by cost

Dijkstra is BFS with the FIFO queue replaced by a min-heap ordered by accumulated cost. When all weights are equal the two coincide — which is exactly why BFS works in Word Ladder and fails here.

Dijkstra's invariant: the first pop of a node is final, because every remaining entry costs at least as much and can only grow. That argument requires non-negative weights.

Dijkstra generalises beyond addition

Question 4 is the surprise. The path cost there is a max, not a sum — the time a route becomes swimmable is its highest elevation. Dijkstra still works, because its correctness needs only that extending a path never lowers its cost:

max(a, b) >= a        so the invariant holds

That unlocks minimax paths, maximum-capacity paths, and probability products — none of which are additive.

Where the obvious choice is wrong

Question	Obvious	Why it fails	Correct
1	greedy smallest-next	strands tickets at a dead end	Hierholzer's — record dead ends, don't backtrack
6	Dijkstra	a hop cap breaks first-pop-is-final	Bellman-Ford with bounded rounds

With a hop budget, a cheaper route may use too many hops to continue — so a pricier short route must stay available, and one best-cost-per-node can't represent both. Bellman-Ford bounds the rounds instead: k + 1 of them, each reading the previous round's snapshot so exactly one edge is added per round.

Verified: omitting that snapshot returns 200 for a k = 0 query whose correct answer is 500 — a two-flight route reported as reachable with zero stops.

Prim's vs Kruskal's

Grow one tree, taking the cheapest outgoing edge

	Kruskal's	Prim's
Needs the edge list	yes, all `E`	no — generate on demand
Cost	`O(E log E)`	`O(E log V)` heap, or `O(V²)` array
Best for	sparse graphs	dense graphs

Question 2's graph is complete — n(n−1)/2 implicit edges — so array-based Prim's wins: O(V²) time, O(V) space, no edge list. On a complete graph a heap skips nothing, so the log factor is pure overhead.

Both are correct by the cut property: the cheapest edge crossing any partition of the nodes belongs to some MST, so the greedy can never rule out an optimum.

Hard Reconstruct Itinerary LC 332 11 min Medium Min Cost to Connect All Points LC 1584 13 min Medium Network Delay Time LC 743 11 min Hard Swim in Rising Water LC 778 11 min Hard Alien Dictionary LC 269 11 min Medium Cheapest Flights Within K Stops LC 787 12 min

The traps

Trap	Symptom
Greedy smallest-next itinerary (Q1)	Strands tickets; naive greedy is almost right
`ArrayList.add(0, x)` for the route (Q1)	`O(E²)` instead of `O(E log E)`
Kruskal's on a complete graph (Q2)	500,000 edge objects built and sorted
BFS on weighted edges (Q3)	Fewest hops ≠ cheapest
Arithmetic on `Integer.MAX_VALUE` (Q3, Q6)	Overflows negative; looks like a bargain
Taking more than the first differing char (Q5)	Invents constraints; false cycles
Missing the prefix check (Q5)	`["abc","ab"]` returns a plausible order
`List` instead of `Set` for adjacency (Q5)	Double-counted in-degree; letter never released
Plain Dijkstra with a hop cap (Q6)	Wrong answer, not slow
Relaxing in place (Q6)	Silently exceeds the hop budget
`k` rounds instead of `k + 1` (Q6)	Off by one stop

Verification

Every snippet compiled and cross-checked against an independent implementation — 1,800+ randomized cases:

Q1 against a backtracking reference on randomly generated Eulerian graphs
Q2 across three implementations — array Prim's, heap Prim's, and Kruskal's
Q3 Dijkstra against Bellman-Ford
Q4 max-Dijkstra against binary search on the answer
Q5 verified semantically: every derived alphabet order was re-checked by re-sorting the input words under it and confirming they come out in the given sequence
Q6 against a depth-capped DFS reference

One deliberately-broken variant confirms the headline trap: relaxing in place rather than from a snapshot returns 200 for a k = 0 query whose answer is 500.