16 — Advanced Graphs

Six named algorithms cover this section. Each answers exactly one question. The skill is matching the question to the algorithm, then recalling the template.

Dijkstra — shortest path with weights

Why BFS isn't enough

BFS finds shortest paths by edge count. With weights, the fewest-edges path may be expensive:

A ──1──→ B ──1──→ C        total cost 2, two edges
A ────────10─────→ C       total cost 10, ONE edge

BFS finds the one-edge path (cost 10). We want the two-edge path (cost 2).

The idea

Dijkstra is BFS with a priority queue instead of a plain queue. Rather than exploring by edge count, it always expands the cheapest node discovered so far.

Why that greedy choice is safe: with non-negative weights, when you pop the cheapest unfinalized node, no other route could reach it more cheaply — any alternative route would have to pass through a node that's already more expensive, and adding non-negative edges can only increase the total. So its distance is final.

// Network Delay Time: earliest time all nodes receive a signal from node k
List<List<int[]>> adj = new ArrayList<>();          // adj.get(u) = list of {v, weight}
for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
for (int[] t : times) adj.get(t[0]).add(new int[]{t[1], t[2]});

int[] dist = new int[n + 1];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[k] = 0;

PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));  // {node, dist}
pq.offer(new int[]{k, 0});

while (!pq.isEmpty()) {
    int[] cur = pq.poll();
    int node = cur[0], d = cur[1];

    if (d > dist[node]) continue;                   // LAZY DELETION — stale entry, skip

    for (int[] edge : adj.get(node)) {
        int next = edge[0], nd = d + edge[1];
        if (nd < dist[next]) {                      // RELAXATION: found a cheaper route
            dist[next] = nd;
            pq.offer(new int[]{next, nd});
        }
    }
}

int ans = 0;
for (int i = 1; i <= n; i++) {
    if (dist[i] == Integer.MAX_VALUE) return -1;    // unreachable
    ans = Math.max(ans, dist[i]);
}
return ans;

Four points that separate a working Dijkstra from a shaky one

1. if (d > dist[node]) continue; — lazy deletion.

Java's PriorityQueue has no efficient "decrease-key" operation. So when we find a better route to a node already in the heap, we just push a second entry with the better distance. The old entry is now stale.

Since the heap is a min-heap, the better entry surfaces first. When the stale one eventually pops, d > dist[node] catches it and we skip. Without this line the algorithm still terminates but wastes work re-expanding nodes.

2. Non-negative weights are required.

A negative edge could improve an already-finalized node, breaking the greedy invariant. If negatives are possible, use Bellman-Ford. State this constraint unprompted — it's the most common Dijkstra follow-up.

3. Unreachable nodes keep Integer.MAX_VALUE. Check for them before aggregating.

4. The answer here is the MAXIMUM of shortest distances, not the sum — the signal has arrived everywhere only once the slowest node receives it.

Modified Dijkstra — minimize the maximum edge

Swim in Rising Water: you can move to a neighbouring cell once the water level reaches its elevation. The time to reach the end is the highest elevation on your path. Minimize it.

The only change: relaxation uses max instead of +.

int[][] time = new int[n][n];
for (int[] row : time) Arrays.fill(row, Integer.MAX_VALUE);
time[0][0] = grid[0][0];

PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));  // {t, r, c}
pq.offer(new int[]{grid[0][0], 0, 0});

while (!pq.isEmpty()) {
    int[] cur = pq.poll();
    int t = cur[0], r = cur[1], c = cur[2];
    if (r == n - 1 && c == n - 1) return t;
    if (t > time[r][c]) continue;

    for (int[] d : DIRS) {
        int nr = r + d[0], nc = c + d[1];
        if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
        int nt = Math.max(t, grid[nr][nc]);         // MAX, not sum — the ONLY change
        if (nt < time[nr][nc]) {
            time[nr][nc] = nt;
            pq.offer(new int[]{nt, nr, nc});
        }
    }
}
return -1;

Why the greedy argument survives: max is also monotonic — extending a path can never decrease its maximum. That's the property Dijkstra actually needs, not addition specifically.

The alternative framing: binary search the water level, and BFS to test whether the end is reachable at that level. O(n² log(n²)), equally acceptable. Offering both — and noting they're the same problem seen as "search the answer" versus "search the graph" — is a strong answer.

Bellman-Ford — shortest path with an edge-count cap

The idea

Relax every edge in the graph, repeatedly. After round i, dist[v] holds the best cost using at most i edges.

That layering by edge count is exactly what a hop limit needs — and it also handles negative weights, since nothing is ever "finalized" greedily.

// Cheapest Flights Within K Stops — "at most k stops" means at most k+1 edges
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;

for (int i = 0; i <= k; i++) {
    int[] snapshot = dist.clone();               // *** CRITICAL ***
    for (int[] f : flights) {
        int u = f[0], v = f[1], w = f[2];
        if (snapshot[u] == Integer.MAX_VALUE) continue;
        dist[v] = Math.min(dist[v], snapshot[u] + w);
    }
}
return dist[dst] == Integer.MAX_VALUE ? -1 : dist[dst];

dist.clone() is the whole question

Without the snapshot, a path relaxed earlier in the same round could be extended again in that same round — silently using more than k + 1 edges.

Concretely: suppose round 1 relaxes A → B and then, later in the same loop, relaxes B → C using the brand-new dist[B]. You've now used two edges in one round, which was supposed to allow only one.

Reading from snapshot — the previous round's values — enforces "exactly one more edge per round."

Explain this explicitly. Interviewers use this problem specifically to see whether you understand the layering.

Why Dijkstra is wrong here: Dijkstra finalizes nodes by cost. But a cheap path might use too many hops while a pricier one fits the budget — so a node's "best" distance depends on how many edges were spent getting there. Cost alone isn't enough state.

Minimum spanning tree

Connect all n nodes using n − 1 edges at minimum total weight.

Prim's — grow one tree outward

Start from any node. Repeatedly add the cheapest edge leaving the tree you've built so far.

// Min Cost to Connect All Points — a COMPLETE graph, so E = O(n²)
int n = points.length;
boolean[] inTree = new boolean[n];
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));  // {cost, node}
pq.offer(new int[]{0, 0});                        // start at node 0, cost 0

int total = 0, added = 0;
while (added < n) {
    int[] cur = pq.poll();
    int cost = cur[0], node = cur[1];
    if (inTree[node]) continue;                   // lazy deletion again

    inTree[node] = true;
    total += cost;
    added++;

    for (int next = 0; next < n; next++) {        // every other point is a neighbour
        if (inTree[next]) continue;
        int d = Math.abs(points[node][0] - points[next][0])
              + Math.abs(points[node][1] - points[next][1]);   // Manhattan distance
        pq.offer(new int[]{d, next});
    }
}
return total;

Kruskal's — sort edges, union greedily

See 17 — Union-Find.

Choosing between them

Min Cost to Connect All Points is a complete graph — every pair of points is connected — so Prim's is the better fit. Say so when you pick it; that reasoning is the point of the question.

Hierholzer's — Eulerian path (Reconstruct Itinerary)

An Eulerian path uses every edge exactly once. Given plane tickets, reconstruct the itinerary starting at "JFK", breaking ties lexicographically.

Why naive greedy DFS fails

"Always take the lexicographically smallest next destination" can strand you at a dead end with tickets still unused. You'd have to backtrack, which is expensive and fiddly.

The fix

Append a node to the result only when it has no unused outgoing edges — then reverse at the end.

Why this works: if you get stuck at a node, that node must be the end of the route (nothing leaves it). So it belongs at the back. By appending on the way out of the recursion, dead ends naturally land at the end, and the rest of the route assembles in front of them.

Map<String, PriorityQueue<String>> adj = new HashMap<>();
for (List<String> t : tickets) {
    adj.computeIfAbsent(t.get(0), k -> new PriorityQueue<>()).offer(t.get(1));
}

LinkedList<String> route = new LinkedList<>();

private void dfs(String airport, Map<String, PriorityQueue<String>> adj, LinkedList<String> route) {
    PriorityQueue<String> dests = adj.get(airport);
    while (dests != null && !dests.isEmpty()) {
        dfs(dests.poll(), adj, route);        // CONSUME the edge as you take it
    }
    route.addFirst(airport);                  // only after ALL edges here are spent
}
// call: dfs("JFK", adj, route);  route is the answer

Two mechanics:

1. A PriorityQueue per airport yields destinations in lexicographic order automatically, satisfying the tie-break rule for free.
2. addFirst after the loop is the Hierholzer insight. Prepending builds the reversed order in place, so no explicit reverse is needed.

O(E log E) — each edge is consumed once, heap operations cost log.

Alien Dictionary — deriving a graph from comparisons

Given words sorted in an unknown alphabet's order, recover that alphabet.

This is a topological sort where the edges must first be inferred.

Map<Character, Set<Character>> adj = new HashMap<>();
Map<Character, Integer> indegree = new HashMap<>();
for (String w : words)
    for (char c : w.toCharArray()) { adj.putIfAbsent(c, new HashSet<>()); indegree.putIfAbsent(c, 0); }

for (int i = 0; i < words.length - 1; i++) {
    String a = words[i], b = words[i + 1];

    // INVALID INPUT: a longer word cannot precede its own prefix
    if (a.length() > b.length() && a.startsWith(b)) return "";

    for (int j = 0; j < Math.min(a.length(), b.length()); j++) {
        char x = a.charAt(j), y = b.charAt(j);
        if (x != y) {
            if (adj.get(x).add(y)) indegree.merge(y, 1, Integer::sum);
            break;                        // ONLY the first difference is informative
        }
    }
}
// then run Kahn's algorithm; if fewer than all distinct chars are output, return ""

Three details the question is actually testing

1. Only the first differing character yields an edge.

Comparing "abc" and "abd" tells you c < d. It tells you nothing about anything after position 2 — sorting already stopped caring once it found a difference. The break is mandatory; without it you'd invent constraints that don't exist.

2. The prefix case is invalid input, not merely edge-less.

["abc", "ab"] can never be correctly sorted — a prefix must always come before the longer word, in any alphabet. This produces no edges, so a naive solution would happily return some order. Missing this is the standard failure.

3. adj.get(x).add(y) guarded by a Set.

If the same relation appears twice, adding the edge twice would double-count the indegree and the node would never reach 0. Set.add returning false on a duplicate prevents that.

Ambiguous orderings are fine — if multiple valid alphabets exist, any topological order is a correct answer. Mention it rather than worrying about it.

Choosing the algorithm

Reach for BFS first. If all weights are equal, Dijkstra degenerates into BFS with heap overhead. Using it anyway reads as pattern-matching rather than understanding.

Complexity summary