skip to content

Kruskal's on a disconnected site graph: what comes back, and what should the planner do?

level: seniorimportance: should knowfreq 36%

answer

  1. Nothing throws — that is the problem
  2. Count the edges the algorithm actually accepted
  3. V minus one, or V minus components?
  4. A cheaper plan that dropped a site
  5. Validate connectivity before paying for the sort

basics

~20 s

Kruskal's silently returns a minimum spanning forest: one optimal tree per component, with V minus c edges instead of V minus one. The planner must compare the accepted-edge count against V minus one and report the unreachable sites.

solid answer

~50 s

On disconnected input nothing throws. Kruskal's walks the sorted edges, accepts every edge joining two different components, and simply runs out of edges before reaching `V-1` accepts — the result is a **minimum spanning forest**, one optimal tree per component. That output looks great by cost and is wrong by intent: an island office with no candidate trench at all just quietly vanishes from the plan. The detection is one comparison — accepted edges equals `V - 1` for a connected graph, and `V - c` for `c` components — so the planner should check that count (or count components directly) and fail loudly, naming which sites are unreachable. Prim's has the same problem with a different shape: started from one node, it spans only that node's component and never notices the rest. Whichever you use, connectivity is a precondition to validate on input, not an outcome to hope for.

code

pseudocode · 11 lines
pseudocode
sort edges by weight ascending
accepted = 0
for each edge (u, v) in sorted order:
    if find(u) != find(v):
        union(u, v)
        output edge (u, v)
        accepted = accepted + 1
        if accepted == length(vertices) - 1:
            break
...
return output

go deeper

for a junior

Know that a spanning tree only exists when the graph is connected, and that a graph in several pieces yields one tree per piece rather than an error.

for a middle

Explain the arithmetic that detects it — a forest over V nodes with c components has exactly V minus c edges — and where in the edge loop that check has to be added.

for a senior

Treat connectivity as an input precondition: validate it before the expensive sort, fail with the names of the unreachable sites, and never let a partial plan reach a caller expecting a full one.

for a principal

Decide what the product owes the caller — a hard failure or an explicit multi-component deliverable — and make the interface say which, so no downstream team can mistake a cheaper forest for a cheaper plan.

## The failure mode: a correct answer to the wrong question Run a cabling planner over a set of branch offices where one site, on an island, has no candidate trench route to anywhere. The greedy edge walk sorts every candidate link by cost, accepts each one whose endpoints are still in separate components, and finishes when the edge list is exhausted. No exception is raised. No flag is set. What comes back is a **minimum spanning forest**: for each connected component, the minimum spanning tree of that component. Every tree in it is genuinely optimal for its own component. And the plan is cheaper than the real answer, because it silently dropped a site. That is the dangerous shape of this bug — the output passes a cost review, passes a "no cycles" check, and passes a "looks like a tree" eyeball. It fails only against intent. ## The arithmetic that catches it On a graph with `V` nodes and `c` connected components, a spanning forest has exactly `V - c` edges. For a connected graph `c = 1`, giving the familiar `V - 1`. So: - **Detection is one integer comparison.** Count accepted edges; if it is not `V - 1`, the input was disconnected, and `V - (accepted count)` tells you how many components you got. - The count also tells you *how bad* it is: two components might mean a single missing link between two campuses; ten components means the candidate-link data is broken upstream. - To go further and *name* the unreachable sites, read the component identity of every node after the run and group by it; the components are already materialized by the algorithm's own merges. The pseudocode fragment above shows why the check has to be added deliberately: the loop's early exit fires when `accepted` reaches `V-1`, but nothing on the other path — the loop simply ending because the edge list ran out — distinguishes success from a forest. ## The other algorithm fails differently Growing a single tree from a start node behaves worse in one respect and better in another. Started at one office, it explores only that office's component; its frontier queue empties, and it returns a tree spanning fewer than `V` nodes. So it also fails silently, and it also needs an explicit "did I reach every node?" check. The difference is what you learn from the failure. The forest-building approach hands you *all* the components and their internal optimal trees in one pass, which is directly useful: you can report "here are your four isolated clusters and the cheapest way to wire each internally." The tree-growing approach tells you only that one component was smaller than the whole graph, and you would have to restart it from an unvisited node repeatedly to enumerate the rest. ## What the feature should actually do There is no universal right answer here, which is why it is a design conversation rather than a lookup: 1. **Fail loudly by default.** A planning tool whose input is supposed to describe a connectable network should treat disconnection as invalid input, name the offending sites, and refuse to emit a plan. Silent partial success is the worst option because it produces a document someone will act on. 2. **Validate connectivity before the cost work.** A single traversal from any node answers "is this connected?" in linear time, well below the cost of sorting all the candidate edges. Cheap precondition, clear error. 3. **Return the forest deliberately, when that is genuinely the product.** Sometimes the islands are expected — separate regions with no cross-region trenching budget. Then the forest is the correct deliverable, but the response must *say* it is a forest, list the components, and carry the per-component costs. The contract, not the algorithm, is what changes. 4. **Do not paper over it with a synthetic edge.** Adding a huge-weight virtual link between components to force `V-1` edges makes the arithmetic pass and buries the real finding in a plan containing a trench nobody can dig. ## Related boundary cases worth naming - **Zero-edge graph.** Every node is its own component; the forest is empty and the accepted count is 0. The check catches it, and the error message should still be about missing candidate links, not about an empty result. - **Self-loops and parallel links.** A self-loop always finds its endpoints already in the same component and is rejected — harmless. Parallel links between the same two sites are fine too: the cheapest is accepted, the rest rejected as cycle-closing. - **A single node.** One office, zero edges: the correct output is an empty edge set, `V - 1 = 0`, so the count check passes and the graph is genuinely connected. Do not special-case it into an error.

  • How would you detect the disconnection without adding a counter to the algorithm?
    Run one linear-time traversal from any node before the cost work and check that it reached every node; that is cheaper than sorting the whole candidate edge list and gives a clear precondition failure. Alternatively, after the run, group nodes by their component identity — the merges already computed it — which additionally names which sites are isolated.
  • How does a tree-growing MST algorithm behave on the same disconnected input?
    It spans only the component containing its start node: the frontier queue empties and it returns a tree over a subset of the nodes, again with no error. It is worse for diagnosis, because one run reveals a single component rather than all of them; enumerating the rest means restarting from an unvisited node repeatedly.
  • The islands are expected — different regions with no cross-region budget. Now what?
    Then the minimum spanning forest is the correct deliverable, and the fix is in the contract rather than the algorithm: return the components explicitly, with a per-component cost and node list, so callers cannot mistake a forest for a spanning plan. What must never happen is returning a forest through an interface that promises a single connected tree.
  • Someone suggests inserting a very high-weight virtual link between components so the edge count works out. Why push back?
    It converts a detectable data problem into an undetectable plan problem. The count check now passes, the output looks like a spanning tree, and buried inside it is a trench nobody can dig at a price nobody quoted. Sentinel weights also distort any cost reporting built on the result. Fail on the precondition instead.

saying these in an interview costs you the question

  • Assumes the algorithm raises an error on disconnected input
  • Believes the accepted edge count is always V minus one
  • Ships the forest through an interface promising a spanning tree
  • Adds a huge sentinel edge to force the count to match
  • Cannot say how many edges a forest with c components has

context

resolving links…