Graph Algorithms for Interviews — Topological Sort, Dijkstra, Union-Find

Beyond plain BFS and DFS, four named algorithms cover essentially every graph question asked in interviews. The skill being tested is picking the right one from the problem statement.

Choosing

The question says	Use
Prerequisites, ordering, "can this be scheduled"	Topological sort
Shortest path, weighted edges	Dijkstra
Shortest path, unweighted	BFS
Are these connected / merge groups	Union-Find
Connect everything at minimum total cost	MST (Prim or Kruskal)
Shortest path with negative weights, or ≤ k edges	Bellman-Ford

Topological sort

An ordering where every edge points forward. Only exists on a DAG — so the same algorithm that produces the order also detects cycles, which is why Course Schedule and Course Schedule II are the same problem.

Kahn's algorithm (BFS over in-degrees) is the one to write:

from collections import deque

def topo_sort(n, edges):
    adj = [[] for _ in range(n)]
    indegree = [0] * n
    for u, v in edges:                 # u must come before v
        adj[u].append(v)
        indegree[v] += 1

    queue = deque(i for i in range(n) if indegree[i] == 0)
    order = []

    while queue:
        node = queue.popleft()
        order.append(node)
        for nxt in adj[node]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:     # every prerequisite satisfied
                queue.append(nxt)

    return order if len(order) == n else []     # short = there is a cycle

int[] topoSort(int n, int[][] edges) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    int[] indegree = new int[n];

    for (int[] e : edges) {        // e[0] must come before e[1]
        adj.get(e[0]).add(e[1]);
        indegree[e[1]]++;          // the DESTINATION's in-degree rises
    }

    Deque<Integer> queue = new ArrayDeque<>();
    for (int i = 0; i < n; i++) if (indegree[i] == 0) queue.add(i);

    int[] order = new int[n];
    int k = 0;
    while (!queue.isEmpty()) {
        int node = queue.poll();
        order[k++] = node;
        for (int next : adj.get(node)) {
            if (--indegree[next] == 0) queue.add(next);
        }
    }
    // A short result means the leftover nodes form a cycle — this length
    // check IS the cycle detection.
    return k == n ? order : new int[0];
}

vector<int> topoSort(int n, const vector<vector<int>>& edges) {
    vector<vector<int>> adj(n);
    vector<int> indegree(n, 0);

    for (const auto& e : edges) {   // e[0] must come before e[1]
        adj[e[0]].push_back(e[1]);
        indegree[e[1]]++;           // the DESTINATION's in-degree rises
    }

    queue<int> q;
    for (int i = 0; i < n; i++) if (indegree[i] == 0) q.push(i);

    vector<int> order;
    while (!q.empty()) {
        int node = q.front(); q.pop();
        order.push_back(node);
        for (int next : adj[node]) {
            if (--indegree[next] == 0) q.push(next);
        }
    }
    // A short result means a cycle — the length check IS the detection.
    return (int)order.size() == n ? order : vector<int>{};
}

function topoSort(n, edges) {
  const adj = Array.from({ length: n }, () => []);
  const indegree = new Array(n).fill(0);

  for (const [u, v] of edges) {   // u must come before v
    adj[u].push(v);
    indegree[v]++;                // the DESTINATION's in-degree rises
  }

  let queue = [];
  for (let i = 0; i < n; i++) if (indegree[i] === 0) queue.push(i);

  const order = [];
  while (queue.length) {
    const next = [];
    for (const node of queue) {
      order.push(node);
      for (const n2 of adj[node]) {
        if (--indegree[n2] === 0) next.push(n2);
      }
    }
    queue = next;
  }
  // A short result means the leftover nodes form a cycle.
  return order.length === n ? order : [];
}

The length check is the cycle detection: nodes inside a cycle never reach in-degree zero, so they never enter the queue.

Alien Dictionary is the same algorithm with the graph hidden — compare adjacent words,

and the first differing character gives one edge. Watch the invalid-input case where a word is a prefix of a shorter predecessor.

Dijkstra

BFS with a priority queue instead of a plain one, so the cheapest frontier node is expanded first rather than the nearest by hop count.

import heapq

def dijkstra(n, adj, source):
    dist = [float("inf")] * n
    dist[source] = 0
    heap = [(0, source)]

    while heap:
        d, node = heapq.heappop(heap)
        if d > dist[node]:
            continue                    # stale entry, already improved
        for nxt, weight in adj[node]:
            if d + weight < dist[nxt]:
                dist[nxt] = d + weight
                heapq.heappush(heap, (dist[nxt], nxt))

    return dist

int[] dijkstra(int n, List<List<int[]>> adj, int source) {
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[source] = 0;

    PriorityQueue<int[]> heap =
        new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
    heap.offer(new int[]{0, source});

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

        // Heaps cannot update a key, so we push a better entry and skip
        // the outdated one when it surfaces — the lazy-deletion idiom.
        if (d > dist[node]) continue;

        for (int[] edge : adj.get(node)) {
            int next = edge[0], weight = edge[1];
            if (d + weight < dist[next]) {
                dist[next] = d + weight;
                heap.offer(new int[]{dist[next], next});
            }
        }
    }
    return dist;   // requires NON-NEGATIVE weights
}

vector<int> dijkstra(int n, const vector<vector<pair<int,int>>>& adj, int source) {
    vector<int> dist(n, INT_MAX);
    dist[source] = 0;

    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> heap;
    heap.push({0, source});

    while (!heap.empty()) {
        auto [d, node] = heap.top(); heap.pop();
        if (d > dist[node]) continue;   // stale entry, already improved

        for (auto [next, weight] : adj[node]) {
            if (d + weight < dist[next]) {
                dist[next] = d + weight;
                heap.push({dist[next], next});
            }
        }
    }
    return dist;   // requires NON-NEGATIVE weights
}

function dijkstra(n, adj, source) {
  const dist = new Array(n).fill(Infinity);
  dist[source] = 0;

  // No built-in priority queue: this linear scan is O(V²), which is fine
  // for dense graphs. Use a binary heap for a sparse one.
  const visited = new Array(n).fill(false);

  for (let iter = 0; iter < n; iter++) {
    let node = -1;
    for (let i = 0; i < n; i++) {
      if (!visited[i] && (node === -1 || dist[i] < dist[node])) node = i;
    }
    if (node === -1 || dist[node] === Infinity) break;
    visited[node] = true;

    for (const [next, weight] of adj[node]) {
      if (dist[node] + weight < dist[next]) dist[next] = dist[node] + weight;
    }
  }
  return dist;   // requires NON-NEGATIVE weights
}

The d > dist[node] skip is the lazy-deletion idiom: heaps cannot update a key, so you push a better entry and ignore the outdated one when it surfaces.

Dijkstra requires non-negative weights. With negatives, a shorter path can appear after a node is finalised — that is Bellman-Ford's territory. Cheapest Flights Within K Stops is exactly that case: the extra "at most k edges" constraint makes plain Dijkstra unsound, and Bellman-Ford relaxing k+1 times is the clean answer.

Union-Find

Near-constant-time "are these connected" and "merge these groups", with both optimisations:

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]   # path compression
            x = self.parent[x]
        return x

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                                   # already together
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra                               # union by rank
        self.rank[ra] += self.rank[ra] == self.rank[rb]
        return True

class UnionFind {
    private final int[] parent, rank;

    UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
    }

    int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];   // path compression, halving
            x = parent[x];
        }
        return x;
    }

    /** Returns false when the two were ALREADY connected — which means this
        edge closes a cycle. That return value is the useful part. */
    boolean union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;

        if (rank[ra] < rank[rb]) { int t = ra; ra = rb; rb = t; }
        parent[rb] = ra;                     // union by rank
        if (rank[ra] == rank[rb]) rank[ra]++;
        return true;
    }
}

class UnionFind {
    vector<int> parent, rank_;
public:
    UnionFind(int n) : parent(n), rank_(n, 0) {
        iota(parent.begin(), parent.end(), 0);
    }

    int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];   // path compression, halving
            x = parent[x];
        }
        return x;
    }

    // Returns false when already connected — i.e. this edge closes a cycle.
    bool unite(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;

        if (rank_[ra] < rank_[rb]) swap(ra, rb);
        parent[rb] = ra;                     // union by rank
        if (rank_[ra] == rank_[rb]) rank_[ra]++;
        return true;
    }
};

typedef struct { int* parent; int* rank; } UnionFind;

UnionFind* ufCreate(int n) {
    UnionFind* uf = malloc(sizeof(UnionFind));
    uf->parent = malloc(n * sizeof(int));
    uf->rank = calloc(n, sizeof(int));
    for (int i = 0; i < n; i++) uf->parent[i] = i;
    return uf;
}

int ufFind(UnionFind* uf, int x) {
    while (uf->parent[x] != x) {
        uf->parent[x] = uf->parent[uf->parent[x]];   /* path compression */
        x = uf->parent[x];
    }
    return x;
}

/* Returns 0 when already connected — i.e. this edge closes a cycle. */
int ufUnion(UnionFind* uf, int a, int b) {
    int ra = ufFind(uf, a), rb = ufFind(uf, b);
    if (ra == rb) return 0;

    if (uf->rank[ra] < uf->rank[rb]) { int t = ra; ra = rb; rb = t; }
    uf->parent[rb] = ra;                             /* union by rank */
    if (uf->rank[ra] == uf->rank[rb]) uf->rank[ra]++;
    return 1;
}

class UnionFind {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank = new Array(n).fill(0);
  }

  find(x) {
    while (this.parent[x] !== x) {
      this.parent[x] = this.parent[this.parent[x]];   // path compression
      x = this.parent[x];
    }
    return x;
  }

  /** Returns false when the two were ALREADY connected — meaning this edge
      closes a cycle. That return value is the useful part. */
  union(a, b) {
    let ra = this.find(a), rb = this.find(b);
    if (ra === rb) return false;

    if (this.rank[ra] < this.rank[rb]) [ra, rb] = [rb, ra];
    this.parent[rb] = ra;                             // union by rank
    if (this.rank[ra] === this.rank[rb]) this.rank[ra]++;
    return true;
  }
}

Path compression plus union by rank gives O(α(n)) amortised — effectively constant.

union returning False is the useful part: it means the two nodes were already connected, so adding this edge creates a cycle. Number of Connected Components is n minus the number of successful unions; Graph Valid Tree is "exactly n - 1 edges and no union ever fails".

Minimum spanning tree

Min Cost to Connect All Points — connect every node at the lowest total cost.

Kruskal: sort all edges by weight, add each one whose endpoints are not already

connected (that is union-find's False again). O(E log E).

Prim: grow one tree, repeatedly taking the cheapest edge leaving it, via a min-heap.

O(E log V), and better on dense graphs — a complete graph of points, for instance, where materialising all E edges for Kruskal is wasteful.

Complexity

Topological sort O(V + E). Dijkstra O(E log V). Union-find O(α(n)) per operation. Kruskal O(E log E), Prim O(E log V). Bellman-Ford O(V × E). Building the adjacency list is O(V + E) and is worth doing explicitly rather than scanning an edge list repeatedly.

Mistakes that cost the round

Reversing edge direction in topological sort. u → v means "u before v", so v's

in-degree increases.

Dijkstra with negative weights. It is simply wrong, not just slow.
Skipping the stale-entry check, which re-expands nodes and can turn into a timeout.
Union-find without path compression, degrading to O(n) per find.
Forgetting the cycle check. Course Schedule is unsolvable, not merely unordered,

when a cycle exists — the length comparison is the answer, not an afterthought.

What to drill

Course Schedule → Course Schedule II — cycle detection, then the order.
Number of Connected Components — union-find, or DFS.
Graph Valid Tree — connectivity plus the edge count.
Network Delay Time — Dijkstra, plainly.
Cheapest Flights Within K Stops — Bellman-Ford with a hop limit.
Min Cost to Connect All Points — Prim on a dense graph.
Alien Dictionary — build the graph, then topologically sort it.
Word Ladder II — BFS for the distances, then backtrack every shortest path.

All on the 22 DSA Patterns sheet.

Frequently asked

How does topological sort detect a cycle?

Kahn's algorithm only enqueues a node once its in-degree reaches zero, which requires every prerequisite to have been processed. Nodes inside a cycle can never reach zero, so they never enter the queue. If the produced order is shorter than the node count, the leftover nodes form a cycle.

When can't I use Dijkstra?

When any edge weight is negative — Dijkstra finalises a node's distance when it is popped, and a negative edge can improve it later, making the result wrong. Use Bellman-Ford instead. Bellman-Ford is also the right choice when the path is constrained to at most k edges, as in Cheapest Flights Within K Stops.

What does union-find give you that DFS does not?

Incremental connectivity. Union-find answers 'are these two connected' in near-constant time while edges are still being added, which DFS cannot do without re-traversing. It also detects cycles for free — a union whose endpoints already share a root means the new edge closes a loop — and that is the core of Kruskal's MST algorithm.

Graphs