How do you approach graph based optimization problems in interviews?
Catch-all category. Common forms: shortest path (BFS for unweighted, Dijkstra for weighted, Bellman-Ford for negative edges, A* with heuristic), minimum spanning tree (Kruskal/Prim), max-flow/min-cut (Ford-Fulkerson), strongly connected components (Tarjan/Kosaraju), topological sort (DFS or Kahn). Recognize the problem shape, then pick the algorithm.
"Graph optimization" is a category, not a single problem. Interviewers want to see you recognize the problem shape and pick the right algorithm.
Recognize the shape
| Shape | Algorithm |
|---|---|
| Shortest path, unweighted | BFS |
| Shortest path, weighted, non-negative | Dijkstra (priority queue) |
| Shortest path, can have negative edges | Bellman-Ford |
| Shortest path with heuristic (e.g., grid + Manhattan) | A* |
| All-pairs shortest paths | Floyd-Warshall (dense) or N × Dijkstra (sparse) |
| MST (cheapest connecting tree) | Kruskal (with union-find) or Prim |
| Max flow / Min cut | Ford-Fulkerson / Edmonds-Karp |
| Topological order (DAG) | Kahn's (BFS) or DFS post-order |
| Strongly connected components | Tarjan or Kosaraju |
| Detect cycle | DFS with colors / union-find |
| Bipartite check | BFS / DFS 2-coloring |
| Articulation points / bridges | Tarjan |
| Connected components | BFS / DFS / union-find |
Shortest path (most common)
BFS — unweighted
function bfsShortest(graph, start, target) {
const queue = [[start, 0]];
const visited = new Set([start]);
while (queue.length) {
const [node, dist] = queue.shift();
if (node === target) return dist;
for (const n of graph[node]) {
if (!visited.has(n)) { visited.add(n); queue.push([n, dist + 1]); }
}
}
return -1;
}Dijkstra — weighted, non-negative
function dijkstra(graph, start) {
const dist = new Map([[start, 0]]);
const pq = new MinHeap([[0, start]]); // [distance, node]
while (pq.size) {
const [d, node] = pq.pop();
if (d > (dist.get(node) ?? Infinity)) continue;
for (const [n, w] of graph[node]) {
const nd = d + w;
if (nd < (dist.get(n) ?? Infinity)) {
dist.set(n, nd);
pq.push([nd, n]);
}
}
}
return dist;
}- Time O((V+E) log V) with a binary heap.
- Doesn't work with negative weights.
A* — with heuristic
Dijkstra + add a heuristic estimate to the priority. Heuristic must be admissible (never overestimates). For a grid: Manhattan or Euclidean distance to the goal.
MST
Kruskal
Sort edges by weight; add edge if it doesn't form a cycle (union-find).
Prim
Like Dijkstra but track "cheapest edge to add" — grow the MST one node at a time.
Topological sort
function topoSort(graph) {
const inDegree = new Map();
for (const node of Object.keys(graph)) inDegree.set(node, 0);
for (const [node, neighbors] of Object.entries(graph)) {
for (const n of neighbors) inDegree.set(n, (inDegree.get(n) ?? 0) + 1);
}
const queue = [...inDegree.entries()].filter(([_, d]) => d === 0).map(([n]) => n);
const order = [];
while (queue.length) {
const node = queue.shift();
order.push(node);
for (const n of graph[node]) {
inDegree.set(n, inDegree.get(n) - 1);
if (inDegree.get(n) === 0) queue.push(n);
}
}
return order.length === Object.keys(graph).length ? order : null; // null = cycle
}Interview framing
"Map the problem to a canonical shape, then pick the algorithm. Shortest path with no weights: BFS. Weighted with non-negative edges: Dijkstra with a priority queue. With a heuristic (grid pathfinding): A*. Negative edges: Bellman-Ford. MST: Kruskal with union-find or Prim. Dependency ordering: topological sort via Kahn's or DFS post-order. Cycle / SCC / articulation point: DFS-with-coloring or Tarjan. The trick is recognizing the shape from the problem description — 'find the cheapest path', 'is there a route', 'order tasks by dependency', 'minimum cost to connect everything' — and picking the textbook algorithm rather than reinventing."
Follow-up questions
- •Why doesn't BFS work for weighted shortest path?
- •When would you choose A* over Dijkstra?
- •Walk through Kruskal vs Prim — when is each better?
- •How do you detect a cycle in a directed graph efficiently?
Common mistakes
- •BFS on weighted graphs.
- •Dijkstra on graphs with negative edges.
- •Forgetting the priority queue in Dijkstra — falls back to O(V²).
- •Treating undirected and directed cycle detection the same.
Performance considerations
- •Algorithm choice dominates. Dense vs sparse: matrix vs adjacency list. Heap implementation in Dijkstra (binary, Fibonacci) affects log factor.
Edge cases
- •Disconnected graphs.
- •Cycles in supposed DAGs (topological sort returns partial).
- •Multi-edge / self-loops.
Real-world examples
- •Map routing (Dijkstra/A*).
- •Build dependency graph (topological sort).
- •Network optimization (max flow).