Foundations — Minimum Spanning Tree — Kruskal's (Union-Find), Prim's (priority queue)

Before you can follow Kruskal or Prim, you must be able to look at a symbol like $(w,u,v)$, or the phrase "same component", or $O(E\log V)$, and instantly picture what it means. This page builds every one of those from nothing, in an order where each idea leans on the one before it.

1. A vertex — the dot

The whole set of vertices is written $V$. When we say "there are $V$ vertices" we are (slightly loosely) using the same letter $V$ for both the set and its size (how many dots there are).

WHY the topic needs it: an MST must "touch every vertex". If you cannot picture a vertex as a dot, the phrase "touch every dot exactly once" has nothing to hold onto.

2. An edge — the line between two dots

The whole set of edges is written $E$, and $E$ also stands for how many edges there are.

3. Undirected — the line has no arrow

WHY the topic needs it: the parent note's biggest "steel-manned error" is thinking MSTs work on directed graphs. They do not. The very definition of MST assumes every edge is two-way. If edges had arrows, "connecting two islands" would become ambiguous — which direction? So we insist on undirected from the start. (The directed cousin is a different beast, stored differently too.)

4. Weight — a price tag on the line

So $(0,1,1)$ means: an edge between vertex $0$ and vertex $1$, costing $1$.

WHY the topic needs it: the word "Minimum" in MST is entirely about these numbers. No weights, no notion of "cheapest".

5. A weighted undirected graph — dots + priced two-way lines

This picture is the exact graph the parent uses for its worked example. Keep it in your head; every later idea points back to it.

6. Connected — you can reach everyone

WHY the topic needs it: an MST only exists if the graph is connected. If two clumps of islands have no bridge between them at all, no set of edges can ever join them, so "spanning" everything is impossible.

7. Component — an isolated clump

WHY the topic needs it: this is the heartbeat of Kruskal. Every time Kruskal considers an edge $(u,v)$ it asks "are $u$ and $v$ already in the same component?" If yes, connecting them again just makes a loop — skip it. That single question is answered by Disjoint Set Union (Union-Find).

8. Cycle — a wasteful loop

9. Tree and Spanning Tree — connected with zero waste

10. The Minimum Spanning Tree itself

11. Greedy — take the best-looking bite now

12. A cut — split the dots into two teams

WHY the topic needs it: the parent's entire correctness proof rides on the cut property — the cheapest crossing edge of any cut is safe to add. You cannot read that theorem until "cut", "$V\setminus S$", and "crossing edge" are pictures, not symbols.

13. Reading the cost notation $O(E\log V)$

Since a graph has at most $V^2$ edges, $\log E\le \log (V^2)=2\log V$, which is why $O(E\log E)$ and $O(E\log V)$ are treated as the same order.

14. Two engines you'll call by name

• $\alpha (V)$ — the inverse Ackermann function. Grows so unimaginably slowly it is effectively constant ($\le 4$ for any graph in the universe). It measures the cost of one Union-Find operation.
• A min-heap / priority queue — a data structure that always hands you its smallest element fast. This is Prim's engine; details in Priority Queue (Binary Heap).
• Prim's heap skeleton is identical to Dijkstra's Algorithm — the only difference is what number you store as the key (edge weight vs. path distance).

Prerequisite map

Equipment checklist

Test yourself — you are ready for the parent page only if each reveal feels obvious.

Connections

• Parent topic
• Disjoint Set Union (Union-Find) — answers "same component?" in near-constant time.
• Priority Queue (Binary Heap) — hands Prim the cheapest crossing edge fast.
• Cut Property and Cycle Property — the theorem that makes greed correct.
• Greedy Algorithms — why local-best is global-best here.
• Graph Representations — edge list vs adjacency list.
• Dijkstra's Algorithm — the same heap skeleton as Prim.