Algorithms from zero
Graphs: code and bug reading
Crux Read graph code and a build log, predict the behaviour, and pick the highest-leverage fix: a visited-set bug, a BFS distance bug, Dijkstra on negative edges, and a topological-sort cycle.
Your altitude — climbing toward senior
ZeroJuniorMiddleSenior
You are at senior altitude — in orbitGraph bugs hide in where you mark a vertex, which queue you pop from, and which weights you trust. Read each snippet, predict what it does on a cyclic or weighted graph, and choose the fix a senior engineer would make first.
Goal
Practise the loop you run on every graph defect: trace the snippet on a small cyclic or weighted example, find the invariant it violates, and reach for the smallest correct fix.
Snippet 1 — DFS that hangs
function dfs(v, adj, visited) {
for (const w of adj[v]) { // mark is AFTER the recurse below
if (!visited.has(w)) {
dfs(w, adj, visited);
}
}
visited.add(v); // marked only on the way out
}
// adj has a cycle: { 0: [1], 1: [2], 2: [0] } Quiz
Completed
Run this on the cyclic graph 0->1->2->0 starting at 0. What happens, and what is the fix?
Heads-up Post-order PUSH for topo sort happens after also guarding entry with a visited check at the top. Here there is no entry mark at all, so the cycle re-enters 0 forever. Mark on entry to prevent re-entry.
Heads-up It never terminates: with no mark before the recursive call, 0->1->2->0->1->2... recurses without bound until the stack overflows. The mark must precede the neighbor loop.
Heads-up A Set is a perfectly valid visited structure. The defect is timing — marking after recursion instead of before — not the data type.
Snippet 2 — BFS shortest path that reports wrong distances
function bfs(src, adj) {
const dist = { [src]: 0 };
const queue = [src];
while (queue.length) {
const v = queue.shift();
for (const u of adj[v]) {
dist[u] = dist[v] + 1; // set every time we see u
queue.push(u); // and enqueue every time
}
}
return dist;
} Quiz
Completed
On a graph where a vertex has several in-edges, this BFS over-counts distances and may not terminate on a cycle. What is the precise bug?
Heads-up A neighbor is one edge FARTHER from the source, so dist[v] + 1 is correct. The real bug is the missing already-visited guard, which lets later, longer arrivals overwrite the first (shortest) one.
Heads-up Plain BFS computes correct unweighted shortest paths precisely because first arrival is shortest — but only if you guard against re-visiting. The algorithm is right; this implementation forgot the guard.
Heads-up shift() already removes from the FRONT (FIFO), which is correct for BFS. Popping the end would make it a stack (DFS). The bug is the missing visited check, not the queue end.
Snippet 3 — Dijkstra on a graph with a refund edge
// adj as [neighbor, weight]: A:[[B,1]], B:[[C,-3]], A:[[C,4]]
// settled is a Set; once a vertex is popped it is final
const [d, u] = heap.pop();
if (settled.has(u)) continue;
settled.add(u); // u's distance is LOCKED here
for (const [v, w] of adj[u]) {
if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; heap.push([dist[v], v]); }
} Quiz
Completed
With the edge B->C of weight -3, Dijkstra settles C via A->C (cost 4) before discovering A->B->C (cost 1 + (-3) = -2). What is the root issue, and the correct fix?
Heads-up Flipping the sign changes the problem: a -3 refund is not the same as a +3 cost, and the shortest paths would be wrong. Negative edges need an algorithm that tolerates them (Bellman-Ford), not a sign hack.
Heads-up Relaxing settled vertices breaks termination guarantees and still does not give a correct shortest-path proof under negatives — it can loop on a negative cycle. The structural answer is Bellman-Ford, not removing the guard.
Heads-up Using <= only adds redundant equal-cost updates; it does not repair the settle invariant under negative edges. The issue is negative weights versus Dijkstra, fixed by Bellman-Ford.
Snippet 4 — topological sort that returns garbage on a cycle
function topo(adj) {
const inDeg = {};
for (const v in adj) inDeg[v] = 0;
for (const v in adj) for (const w of adj[v]) inDeg[w]++;
const q = Object.keys(adj).filter(v => inDeg[v] === 0);
const order = [];
while (q.length) {
const v = q.shift(); order.push(v);
for (const w of adj[v]) if (--inDeg[w] === 0) q.push(w);
}
return order; // returns order unconditionally
}
// adj = { a:[b], b:[c], c:[a], d:[a] } // a->b->c->a is a cycle Quiz
Completed
On this graph (a->b->c->a is a cycle, plus d->a), what does topo return, and what is the correct fix?
Heads-up Kahn's produces a full order only for a DAG. Here the cycle a->b->c->a keeps those three at non-zero in-degree, so only d is emitted. The function must detect the short output as a cycle.
Heads-up d has in-degree 0 (nothing points to d), so d is emitted. The result is the partial ['d'], not empty. The fix is the leftover-count cycle check, not assuming an empty result.
Heads-up Nothing throws — the while loop simply drains the queue and exits with a partial order. The danger is exactly that it fails SILENTLY; you must add the order.length < V check yourself.
Recap
Every snippet failed on one invariant. DFS must mark a vertex on ENTRY, before recursing, or a cycle re-enters forever. BFS shortest path must guard first-arrival (mark on enqueue) so a longer later route never overwrites the shortest. Dijkstra’s settle step is valid only for non-negative weights; a negative edge means Bellman-Ford. And Kahn’s topological sort must check the leftover count — a short output is a cycle, not a valid order. Trace on a tiny cyclic or weighted graph, name the broken invariant, then apply the smallest fix.