Algorithms from zero
Graphs: multiple-choice review
Crux Multiple-choice synthesis across the graphs unit: representation tradeoffs, BFS vs DFS, topological sort, Dijkstra's settle invariant, and union-find.
Your altitude — climbing toward senior
ZeroJuniorMiddleSenior
You are at senior altitude — in orbitSix questions that cut across the whole unit. Each one picks the algorithm or representation a problem actually demands — not a definition to recite, but a modeling decision to defend.
Goal
Confirm you can connect representation choice, traversal order, ordering, weighted shortest paths, and dynamic connectivity — the synthesis the eight lessons built toward.
Quiz
Completed
A social graph has 50 million users and ~200 friendships each (so E is roughly 5 billion directed entries, far below V squared). The hot operation is 'iterate a user's friends'. Which representation, and why?
Heads-up A V-by-V matrix here needs ~2.5 quadrillion cells — impossible to store. The graph is sparse (E much less than V squared), so the list wins on both space and on the actual hot operation, neighbor iteration.
Heads-up An edge list is compact but cannot iterate one user's friends without scanning all E edges. For the 'list a vertex's neighbors' operation it is O(E), far worse than the list's O(degree).
Heads-up At this scale the matrix does not even fit in memory, and neighbor iteration is O(V) on a matrix vs O(degree) on a list. The choice is decisive, not cosmetic.
Quiz
Completed
You must find the route between two map locations with the fewest road segments, ignoring distance. You only need hop count. Which algorithm is the right first reach, and what makes it correct?
Heads-up Dijkstra is correct here but it is overkill: with all weights equal to 1 it degenerates into BFS, paying an extra log V heap factor for nothing. BFS is the right first reach for hop count.
Heads-up DFS visits all reachable vertices but in depth-first order; the first DFS route to a vertex is not the shortest. Only BFS's level-by-level order guarantees fewest edges.
Heads-up Topological sort orders a DAG by dependency direction; it says nothing about hop distance and is undefined on a graph with cycles, which road networks have.
Quiz
Completed
A build system runs Kahn's algorithm over its dependency DAG and the output order lists only 18 of the 20 build targets. What does that tell you?
Heads-up Kahn's never drops a vertex that can legally be ordered. A short output is a definite signal: the leftover vertices form or depend on a cycle, so no valid order exists for them.
Heads-up In-degree-0 vertices are the FIRST to be enqueued and output, not skipped. The missing ones are the opposite: their in-degree never drops to 0 because a cycle keeps feeding them.
Heads-up Appending them produces an order that violates a dependency, because they are in a cycle with no consistent position. The correct response is to report a circular dependency, not fabricate an order.
Quiz
Completed
A pricing graph has some edges that represent refunds (negative cost). An engineer runs Dijkstra and gets answers that are sometimes too high. Why, and what is the fix?
Heads-up Heaps store negative numbers fine. The real defect is the settle invariant: settling commits a distance that a later negative edge could undercut. The bug is algorithmic, not numeric.
Heads-up Dijkstra handles directed graphs correctly. The problem is specifically negative weights, not edge direction. Bellman-Ford, not undirecting the graph, is the fix.
Heads-up Running Dijkstra from every source still applies the broken settle invariant at each run, so negative edges still produce wrong answers. The structural fix is Bellman-Ford.
Quiz
Completed
Edges arrive one at a time over a stream, and after each edge you must answer 'are u and v in the same component yet?' instantly. Which structure fits, and why is re-running BFS the wrong choice?
Heads-up A matrix cell only says whether a DIRECT edge u-v exists, not whether u and v are connected through a path. Reachability still needs a traversal; DSU is what tracks component membership incrementally.
Heads-up It is correct but the cost is O(V + E) per query, repeated for every arriving edge. DSU answers the same query in amortized O(alpha(n)) with no re-traversal — the whole reason DSU exists.
Heads-up Topological sort orders a DAG; it does not answer undirected connectivity, and it is undefined once the stream introduces a cycle. DSU is the dynamic-connectivity structure.
Quiz
Completed
A teammate claims their union-find is O(1) per operation because they added path compression. What is the precise complexity, and what is missing or overstated?
Heads-up Tarjan proved an alpha(n) lower bound for this structure, so it is provably NOT true constant time per call. The honest bound is amortized O(alpha(n)).
Heads-up O(log n) is the bound for union by rank ALONE. With path compression added too, the amortized bound drops below that to O(alpha(n)). Stating O(log n) understates the optimized structure.
Heads-up Path compression SHORTENS paths by repointing nodes toward the root; it improves time, not worsens it. O(n) is the unoptimized degenerate-chain cost, the opposite of what compression gives.
Recap
The unit’s through-line is one modeling decision tree: pick the representation by density (list for sparse, matrix for dense or O(1) edge lookup); pick the traversal by what you need (BFS for fewest-edge paths and levels, DFS for depth and cycle structure); add weights and BFS yields to Dijkstra — but only with non-negative edges, else Bellman-Ford. Topological sort orders a DAG and detects cycles for free, and union-find answers dynamic connectivity in amortized O(alpha(n)) where re-running BFS would be wasteful. Match the algorithm to the problem’s shape before writing a line of code.