Exercise 3: Why Kruskal Needs Cycle-Checking and Prim Doesn't — Possible Solution
====================================================================

WHY KRUSKAL CAN ACCIDENTALLY CREATE A CYCLE
------------------------------
Kruskal's algorithm is greedy on EDGES anywhere in the graph, in
weight order, completely independent of which vertices are
already connected to which. Nothing about "consider the next-
cheapest edge in the whole graph" automatically guarantees that
edge's two endpoints aren't already connected through a different
chain of previously-added edges. This chapter's own worked example
showed exactly this: A-B(4) was skipped because A and B were
already connected via B-C-A, even though A-B itself is a perfectly
normal, real edge in the graph - Kruskal has no way of knowing
that in advance without explicitly checking, which is exactly what
Union-Find's find(u) != find(v) test does.

WHY PRIM CAN NEVER CREATE A CYCLE, EVEN WITHOUT CHECKING
------------------------------
Prim's algorithm only ever considers edges on its own frontier -
edges connecting a vertex ALREADY in the tree to a vertex that is
explicitly tracked as NOT yet in the tree (per this chapter's own
"visited" set). Every single edge Prim's algorithm is even capable
of adding, by construction, has exactly one endpoint inside the
tree and one endpoint outside it. Adding such an edge can only ever
extend the tree by exactly one new vertex - it can never connect
two vertices that are both already in the tree, which is the only
way a cycle could form. The moment a candidate edge's far endpoint
turns out to already be in the visited set (as happened with
Office1-Office2 once Office2 was already reached via Office3 in
Exercise 2), Prim's algorithm simply skips it as "already visited,"
not because it detected a cycle, but because that vertex is
already accounted for.

RESULT
------------------------------
Kruskal's edge-greedy approach can encounter any edge in the graph
in any order, so it genuinely needs an explicit check (Union-Find)
to catch the case where an edge's endpoints are already connected.
Prim's frontier-greedy approach structurally never considers an
edge that could create a cycle in the first place - every edge it
even looks at, by definition, connects the tree to something new,
so no separate cycle check is ever needed.

WHY THIS WORKS AS AN ANSWER
------------------------------
The explanation is grounded in the specific structural difference
between the two algorithms - which edges each one is even capable
of considering - rather than simply asserting Kruskal "needs" a
check and Prim "doesn't," and it reuses concrete evidence already
established earlier in this chapter's own worked examples for
both algorithms.