Why this matters when you build with AI
Ask an AI tool for a minimum spanning tree (the cheapest set of roads that links every town) and you will get code that looks finished. Four errors show up often, and each one gives a wrong number without any crash.
- Kruskal is written without the sort step. On the example graph in this lesson, with the edges in a bad order, the code returned a total of 12. The correct total is 7.
- The second-best tree is defined as "the lightest tree heavier than the MST". On the example this gives 8. The correct answer is 7, because another tree of the same weight exists.
- "Edge in some MST" is read off the one tree the program built. The example's edge 0-2 is not in that tree, so such code says no. A minimum spanning tree that uses it does exist, so the correct answer is yes.
- Prim does not skip stale heap entries (explained below). In the hands-on exercise, this version gives a wrong answer on 1935 of 5000 random small graphs.
Catch these with a brute force: list every set of n - 1 edges, keep the sets that form a tree, and take the answer from that list. It is slow but obviously correct. Compare it with the fast code on many small random graphs. The last part of this lesson does exactly that.
A prompt that states the limits:
Write C++17 code that returns the weight of a minimum spanning tree of a connected
undirected graph with up to 200000 vertices and 200000 edges. Edge weights are integers
from 1 to 10^9. Use long long for the total. Say what your code returns if the graph is
not connected, name the algorithm, and state its time complexity.A good answer uses long long for the total (200000 edges of weight 10^9 add up to 2 * 10^14, which does not fit in a 32-bit int), returns a clear value such as -1 for a disconnected graph, and gives O(m log m) time. Check each of these by reading the code. Then run it against a brute force on small graphs.
Terms used
- A graph has vertices numbered 0 to n - 1 and undirected edges. Each edge joins two vertices and has a weight.
- A spanning tree is a set of n - 1 edges that connects all n vertices and has no cycle. Its weight is the sum of its edge weights.
- A minimum spanning tree (MST) is a spanning tree with the least weight. Several MSTs can exist when weights repeat.
- A cycle is a walk that starts and ends at the same vertex without reusing an edge. A self-loop is an edge from a vertex to itself. Parallel edges are two edges with the same two ends.
- A cut splits the vertices into two groups: a set S and everything else. An edge crosses the cut if one end is in S and the other end is not.
- Disjoint set union (DSU, also called union-find) keeps vertices in groups.
find(x)names the group of x, andunite(a, b)merges the groups of a and b. - A binary heap is a priority queue. It returns its smallest item quickly. In C++,
priority_queuewithgreater<>gives a min-heap.
The idea: two rules that decide each step
The cut property
For any cut, the lightest edge that crosses it belongs to at least one MST. If it is the only edge of that weight across the cut, it belongs to every MST.
A concrete example. The graph has five vertices and seven edges. The edge numbers are used by the code later.
edge ends weight
e0 0-1 1
e1 1-2 2
e2 0-2 2
e3 2-3 3
e4 3-4 1
e5 1-3 4
e6 2-4 5Take the cut S = {3, 4}. Three edges cross it: 2-3 (weight 3), 1-3 (weight 4) and 2-4 (weight 5). The lightest is 2-3, and no other crossing edge has weight 3, so e3 is in every MST. The program output in the hands-on section agrees.
The reason is an exchange argument. Take an MST T that does not contain the lightest crossing edge e. Adding e to T closes a cycle, and that cycle crosses the cut at least twice. One other crossing edge f on the cycle has weight at least the weight of e. Remove f and add e. The result is still a spanning tree, and its weight is no larger. So an MST that contains e exists.
The cycle property
If an edge e is strictly heavier than every other edge on some cycle, then e is in no MST.
Take the cycle 1-2-3-1. Its edges are e1 (weight 2), e3 (weight 3) and e5 (weight 4). Edge e5 is strictly the heaviest, so it is in no MST.
Now take the cycle 0-1-2-0. Its edges are e0 (weight 1), e1 (weight 2) and e2 (weight 2). Two edges tie for the heaviest weight, so neither is forced out. Each of e1 and e2 is in some MST, and neither is in every MST. This tie is the main source of trouble in the later sections.
Kruskal: sort, then take each edge that joins two groups
Kruskal's method (Joseph B. Kruskal, "On the shortest spanning subtree of a graph and the traveling salesman problem", Proceedings of the American Mathematical Society, volume 7, 1956, pages 48 to 50) is short. Sort the edges by weight. Walk through them in that order. Take an edge if its two ends are in different groups, and merge the groups with unite. Skip the edge if its ends are already in the same group, because taking it would close a cycle.
Each step follows from the cut property. When the edge joins two groups, the group on one side is a cut, and this edge is the lightest edge that crosses it among those not yet rejected.
A trace on the example. The sort is stable, so the two weight-1 edges keep their input order: e0, then e4. The same rule applies to the weight-2 edges, e1 then e2.
take e0 (0-1, w 1) groups: {0,1} {2} {3} {4}
take e4 (3-4, w 1) groups: {0,1} {2} {3,4}
take e1 (1-2, w 2) groups: {0,1,2} {3,4}
skip e2 (0-2, w 2) 0 and 2 are already in one group
take e3 (2-3, w 3) groups: {0,1,2,3,4}; four edges taken for five vertices, stop
total = 1 + 1 + 2 + 3 = 7The complexity is O(m log m) for the sort, plus nearly constant time per DSU operation. The DSU in the code uses union by size, which attaches the smaller group under the larger one, and path halving, which shortens the chain to the root while find runs. Tarjan's 1975 analysis of union by size with path compression (Robert Endre Tarjan, "Efficiency of a Good But Not Linear Set Union Algorithm", Journal of the ACM, volume 22, number 2, 1975, pages 215 to 225) gives bounds in terms of the inverse Ackermann function, which grows so slowly that it is effectively constant for any input you will meet. The code section gives the full header.
Prim: grow one tree from vertex 0
Prim's method (Robert C. Prim, "Shortest connection networks and some generalizations", Bell System Technical Journal, volume 36, number 6, 1957, pages 1389 to 1401) starts with vertex 0 alone. At each step it takes the lightest edge that leaves the tree and goes to a vertex outside it, and adds that vertex. The tree's vertices are one side of a cut, so the cut property says that edge is safe.
The heap holds every edge that leaves the tree, as a pair (weight, target vertex). When a pair is popped and its target is already in the tree, the pair is stale. Skip it. This is the same lazy deletion used in the shortest-path lesson.
A trace on the example. This is a hand trace. Its final total matches the program.
start: tree {0}, total 0. Push (1, vertex 1) from e0 and (2, vertex 2) from e2.
pop (1, 1): add 1, total 1. Push (2, vertex 2) from e1 and (4, vertex 3) from e5.
pop (2, 2): add 2, total 3. Push (3, vertex 3) from e3 and (5, vertex 4) from e6.
pop (2, 2): stale, 2 is already in the tree. Skip.
pop (3, 3): add 3, total 6. Push (1, vertex 4) from e4.
pop (1, 4): add 4, total 7. All five vertices are in the tree. Stop.The heap gets at most 2m + 1 pushes, so the time is O(m log m). Without the stale check (the line that skips a vertex already in the tree), a vertex can be added twice, and the total becomes wrong.
The C++17 code
The code is one header, mst.hpp. The blocks below are the file, in order. The DSU and Kruskal come first.
#pragma once
#include <bits/stdc++.h>
using namespace std;
struct Edge {
int u, v;
long long w;
};
// Disjoint set union with path halving and union by size.
struct DSU {
vector<int> p, sz;
explicit DSU(int n) : p(n), sz(n, 1) { iota(p.begin(), p.end(), 0); }
int find(int x) {
while (p[x] != x) {
p[x] = p[p[x]];
x = p[x];
}
return x;
}
bool unite(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return false;
if (sz[a] < sz[b]) swap(a, b);
p[b] = a;
sz[a] += sz[b];
return true;
}
};
// Kruskal: sort edges by weight, take each edge that joins two different components.
// Returns the total weight, or -1 if the graph is not connected.
// If chosen is not null, it receives the indices of the tree edges.
long long kruskal(int n, const vector<Edge>& edges, vector<int>* chosen = nullptr) {
vector<int> order(edges.size());
iota(order.begin(), order.end(), 0);
stable_sort(order.begin(), order.end(),
[&](int a, int b) { return edges[a].w < edges[b].w; });
DSU dsu(n);
long long total = 0;
int used = 0;
if (chosen) chosen->clear();
for (int i : order) {
if (dsu.unite(edges[i].u, edges[i].v)) {
total += edges[i].w;
used++;
if (chosen) chosen->push_back(i);
}
}
return used == n - 1 ? total : -1;
}Prim with a heap and lazy deletion:
// Prim with a binary heap and lazy deletion. Grows one tree from vertex 0.
// Returns the total weight, or -1 if the graph is not connected.
long long prim(int n, const vector<Edge>& edges) {
vector<vector<pair<int, long long>>> adj(n);
for (const Edge& e : edges) {
adj[e.u].push_back({e.v, e.w});
adj[e.v].push_back({e.u, e.w});
}
vector<char> inTree(n, 0);
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;
pq.push({0, 0});
long long total = 0;
int taken = 0;
while (!pq.empty()) {
auto [w, u] = pq.top();
pq.pop();
if (inTree[u]) continue; // stale entry: u was already added through a cheaper edge
inTree[u] = 1;
total += w;
taken++;
for (auto [v, c] : adj[u]) {
if (!inTree[v]) pq.push({c, v});
}
}
return taken == n ? total : -1;
}Maximum weight on a tree path, using binary lifting (a table of ancestors at distances 1, 2, 4 and so on, so that any path is answered in O(log n) steps):
// Maximum edge weight on the tree path between two vertices, by binary lifting.
struct MaxOnPath {
int LOG = 1;
vector<int> depth;
vector<vector<int>> up;
vector<vector<long long>> mx;
MaxOnPath(int n, const vector<Edge>& edges, const vector<int>& tree) {
vector<vector<pair<int, long long>>> g(n);
for (int i : tree) {
g[edges[i].u].push_back({edges[i].v, edges[i].w});
g[edges[i].v].push_back({edges[i].u, edges[i].w});
}
while ((1 << LOG) < n) LOG++;
depth.assign(n, -1);
up.assign(LOG + 1, vector<int>(n, 0));
mx.assign(LOG + 1, vector<long long>(n, LLONG_MIN));
queue<int> q;
q.push(0);
depth[0] = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
for (auto [v, w] : g[u]) {
if (depth[v] < 0) {
depth[v] = depth[u] + 1;
up[0][v] = u;
mx[0][v] = w;
q.push(v);
}
}
}
for (int k = 1; k <= LOG; k++) {
for (int v = 0; v < n; v++) {
int mid = up[k - 1][v];
up[k][v] = up[k - 1][mid];
mx[k][v] = max(mx[k - 1][v], mx[k - 1][mid]);
}
}
}
// u and v must be in the same tree. Use u != v, because the answer for u == v is LLONG_MIN.
long long query(int u, int v) const {
long long best = LLONG_MIN;
if (depth[u] < depth[v]) swap(u, v);
int diff = depth[u] - depth[v];
for (int k = 0; k <= LOG; k++) {
if ((diff >> k) & 1) {
best = max(best, mx[k][u]);
u = up[k][u];
}
}
if (u == v) return best;
for (int k = LOG; k >= 0; k--) {
if (up[k][u] != up[k][v]) {
best = max({best, mx[k][u], mx[k][v]});
u = up[k][u];
v = up[k][v];
}
}
return max({best, mx[0][u], mx[0][v]});
}
};Second-best spanning tree, and the two edge-membership checks:
// Second-best spanning tree: the lightest spanning tree whose edge set differs from the
// tree Kruskal builds. Uses the single-swap rule: for an edge e outside the tree, swapping
// e in for the heaviest tree edge on its path gives weight total + w(e) - maxOnPath(u, v).
// Returns -1 if the graph is not connected or has no second tree.
long long second_best_mst(int n, const vector<Edge>& edges) {
vector<int> tree;
long long total = kruskal(n, edges, &tree);
if (total < 0) return -1;
vector<char> inTree(edges.size(), 0);
for (int i : tree) inTree[i] = 1;
MaxOnPath mop(n, edges, tree);
long long best = LLONG_MAX;
for (int i = 0; i < (int)edges.size(); i++) {
if (inTree[i] || edges[i].u == edges[i].v) continue;
best = min(best, total + edges[i].w - mop.query(edges[i].u, edges[i].v));
}
return best == LLONG_MAX ? -1 : best;
}
// For each edge, true if some MST contains it.
// Rule: edge (u, v, w) is in some MST exactly when u and v are not connected by edges
// of weight strictly less than w. Edges of equal weight are handled as one group.
vector<char> edges_in_some_mst(int n, const vector<Edge>& edges) {
int m = edges.size();
vector<int> order(m);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int a, int b) { return edges[a].w < edges[b].w; });
vector<char> res(m, 0);
DSU dsu(n);
int i = 0;
while (i < m) {
int j = i;
while (j < m && edges[order[j]].w == edges[order[i]].w) j++;
for (int k = i; k < j; k++) {
int e = order[k];
res[e] = dsu.find(edges[e].u) != dsu.find(edges[e].v);
}
for (int k = i; k < j; k++) {
dsu.unite(edges[order[k]].u, edges[order[k]].v);
}
i = j;
}
return res;
}
// For each edge, true if every MST contains it.
// Rule: edge e is in every MST exactly when its ends are not connected by the other
// edges of weight at most w(e). This simple version runs in O(m^2) DSU operations.
vector<char> edges_in_every_mst(int n, const vector<Edge>& edges) {
int m = edges.size();
vector<char> res(m, 0);
for (int i = 0; i < m; i++) {
DSU dsu(n);
for (int j = 0; j < m; j++) {
if (j != i && edges[j].w <= edges[i].w) dsu.unite(edges[j].u, edges[j].v);
}
res[i] = dsu.find(edges[i].u) != dsu.find(edges[i].v);
}
return res;
}Second-best spanning tree
Here "second-best" means the lightest spanning tree whose edge set differs from the MST that Kruskal built. It may have the same weight as the MST.
Use the single-swap rule. Take an edge e that is not in the tree. Adding e to the tree closes a cycle: e plus the tree path between its ends. Remove the heaviest edge f on that path. The result is a spanning tree with weight total + w(e) - w(f). The answer is the smallest such value over all non-tree edges.
Worked on the example. The tree is e0, e4, e1, e3, with total 7.
- e2 (0-2, weight 2): the tree path 0-1-2 uses e0 (weight 1) and e1 (weight 2). The heaviest is 2. New weight: 7 + 2 - 2 = 7.
- e5 (1-3, weight 4): the path 1-2-3 uses e1 (weight 2) and e3 (weight 3). The heaviest is 3. New weight: 7 + 4 - 3 = 8.
- e6 (2-4, weight 5): the path 2-3-4 uses e3 (weight 3) and e4 (weight 1). The heaviest is 3. New weight: 7 + 5 - 3 = 9.
The smallest is 7, and the tree from swapping e1 for e2 has that weight. The program prints Second-best total: 7.
Be exact about the question. If you ask for a tree that is strictly heavier than the MST, the answer for this graph is 8. The program's brute force printed Lightest tree with weight strictly above 7: 8.
Scope of what was checked. The single-swap rule is the usual method for this problem. The lesson does not prove it. We checked it against a brute force over every edge subset on 5000 random graphs, and it matched on every connected graph.
The query maxOnPath uses binary lifting, so each non-tree edge costs O(log n). The total time is O((n + m) log n + m log m).
Edges that appear in some MST, or in every MST
Rule for "some". Edge (u, v, w) is in some MST exactly when u and v are not connected by edges of weight strictly less than w. If they are connected by lighter edges, the new edge closes a cycle whose other edges are all lighter, so the cycle property puts it in no MST. Edges of equal weight must be tested as a group, so that two equal edges do not help each other connect.
Example: e2 (0-2, weight 2). The only lighter edge is e0 (0-1), which does not reach vertex 2. So e2 is in some MST. Kruskal's tree does not contain it, but the tree with e2 instead of e1 is an MST, which matches the second-best check above.
Rule for "every". Edge e is in every MST exactly when its ends are not connected by the other edges of weight at most w(e).
Example: e3 (2-3, weight 3). The other edges of weight at most 3 are e0, e1, e2, e4. They join and , but not 2 with 3. So e3 is in every MST. Example: e1 (1-2, weight 2). The other edges of weight at most 2 include e2 (0-2) and e0 (0-1), which connect 1 and 2 through vertex 0. So e1 is not in every MST.
The program prints these answers for all seven edges:
edge 0 (0-1, w=1) in some MST: yes, in every MST: yes
edge 1 (1-2, w=2) in some MST: yes, in every MST: no
edge 2 (0-2, w=2) in some MST: yes, in every MST: no
edge 3 (2-3, w=3) in some MST: yes, in every MST: yes
edge 4 (3-4, w=1) in some MST: yes, in every MST: yes
edge 5 (1-3, w=4) in some MST: no, in every MST: no
edge 6 (2-4, w=5) in some MST: no, in every MST: noAn edge that is in every MST is in some MST too, and the program's output keeps that order.
Test them against each other
Two independent methods should give the same totals. Kruskal and Prim do not share code paths, so when they agree on many graphs, both are probably right. A brute force gives a third opinion. It also checks the second-best and the two membership tests, which Kruskal and Prim do not cover.
The stress test below draws random graphs with up to 6 vertices, up to 10 edges and weights from 1 to 4. Small weights make ties common, which is where the mistakes live. For each graph it enumerates every set of n - 1 edges, keeps the ones that form a tree, and computes all answers from that list.
#include "mst.hpp"
// Brute force: try every set of n-1 edges, keep the ones that form a spanning tree.
int main() {
mt19937 rng(12345);
const int trials = 5000;
int connected = 0, multiMst = 0, secondDefined = 0, failures = 0;
for (int t = 0; t < trials; t++) {
int n = 1 + rng() % 6;
int m = rng() % 11;
vector<Edge> E;
for (int i = 0; i < m; i++) {
E.push_back({(int)(rng() % n), (int)(rng() % n), 1 + (long long)(rng() % 4)});
}
vector<unsigned> trees;
vector<long long> treeW;
for (unsigned mask = 0; mask < (1u << m); mask++) {
if (__builtin_popcount(mask) != n - 1) continue;
DSU d(n);
bool ok = true;
long long w = 0;
for (int i = 0; i < m && ok; i++) {
if (mask >> i & 1) {
if (!d.unite(E[i].u, E[i].v)) ok = false;
w += E[i].w;
}
}
if (ok) {
trees.push_back(mask);
treeW.push_back(w);
}
}
long long bruteMin = -1;
for (long long w : treeW) bruteMin = (bruteMin < 0) ? w : min(bruteMin, w);
vector<unsigned> mstMasks;
for (size_t k = 0; k < trees.size(); k++) {
if (treeW[k] == bruteMin) mstMasks.push_back(trees[k]);
}
vector<int> chosen;
long long kTotal = kruskal(n, E, &chosen);
long long pTotal = prim(n, E);
unsigned keptMask = 0;
for (int i : chosen) keptMask |= 1u << i;
bool bad = false;
if (kTotal != bruteMin || pTotal != bruteMin) bad = true;
if (bruteMin >= 0) {
connected++;
if (mstMasks.size() > 1) multiMst++;
// Second best: lightest spanning tree whose edge set differs from Kruskal's tree.
long long brute2 = -1;
for (size_t k = 0; k < trees.size(); k++) {
if (trees[k] == keptMask) continue;
if (brute2 < 0 || treeW[k] < brute2) brute2 = treeW[k];
}
if (brute2 >= 0) secondDefined++;
if (second_best_mst(n, E) != brute2) bad = true;
vector<char> some = edges_in_some_mst(n, E);
vector<char> every = edges_in_every_mst(n, E);
for (int i = 0; i < m; i++) {
bool inSome = false, inEvery = true;
for (unsigned mk : mstMasks) {
if (mk >> i & 1) inSome = true;
else inEvery = false;
}
if ((bool)some[i] != inSome || (bool)every[i] != inEvery) bad = true;
}
} else {
// Disconnected graph: every method must report -1.
if (second_best_mst(n, E) != -1) bad = true;
}
if (bad) {
failures++;
if (failures <= 3) {
cout << "MISMATCH in trial " << t << " n=" << n << " m=" << m << "\n";
}
}
}
cout << "trials=" << trials << " connected=" << connected
<< " with two or more MSTs=" << multiMst
<< " with a second-best tree=" << secondDefined
<< " failures=" << failures << "\n";
return failures == 0 ? 0 : 1;
}The demo program that prints the example's totals and the table above uses the same header. Its output is the output shown in this lesson. The stress test printed this on the test machine (g++ 15.2.0 with -O2, on WSL2):
trials=5000 connected=2964 with two or more MSTs=856 with a second-best tree=1813 failures=0The generator is seeded, so these counts should match on any machine with a standard C++17 compiler.
Checking the unique-MST rule (used in the practice problems) against the same kind of brute force on a different seed matched on every connected graph.
Hands-on exercise
Do this on your own machine.
- Make a folder. Save the header above as
mst.hpp, and the stress test asmst_stress.cpp. Compile withg++ -std=c++17 -O2 -Wall -Wextra -o mst_stress mst_stress.cppand run./mst_stress. Expectfailures=0. - Break Prim on purpose. In
mst.hpp, delete the lineif (inTree[u]) continue;. Compile and run the stress test again. Expect manyMISMATCHlines and a final line with a large failure count. In our run it wasfailures=1935. Explain to yourself why: a vertex that was already added can be popped again, and its weight is added twice. - Restore the line. Write your own Kruskal in about 15 lines, without looking at the header. Add a check to the stress test that compares its total with
kruskal. Expect zero mismatches. If you get a mismatch, print the graph for the first failing trial and work out the answer by hand. - Use an AI tool to review your Kruskal with this prompt:
Here is my Kruskal implementation in C++17 for a graph with n vertices and a list of
edges {u, v, w}. Check it line by line for three things: does it sort the edges by
weight, does it skip an edge whose two ends are already in one group, and does it
return -1 when fewer than n - 1 edges are taken. Then give one small input where the
code returns a wrong total, with the total you expect.A good answer points at the exact lines for the three checks. Do not trust its counterexample until your brute force agrees with it.
Common mistakes
- Kruskal without the sort. The example edges, given in a bad order, produced a total of 12 instead of 7. The symptom is a total that changes when the input order changes.
- Prim without the stale check. The stress test showed 1935 failures out of 5000. The symptom is a total that is too large, or a result that depends on the order of equal-weight edges.
- The second-best defined as "strictly heavier". The example gives 8 instead of 7.
- Reading "in some MST" off the one tree you built. The example edge e2 says no, but the correct answer is yes.
- Using
intfor totals. With weights up to 10^9, two edges already exceed the 32-bit limit. Signed integer overflow in C++ is undefined behaviour, so the program may print a wrong value without any error. - Treating -1 as a weight. The functions return -1 for a disconnected graph. If a caller adds that -1 to a sum, the answer is wrong without any error. Check the value before you use it.
- Calling
maxOnPathwith u equal to v. For a self-loop the query returnsLLONG_MIN, and the formula overflows. The code skips self-loops for this reason. - Assuming the MST is unique. Equal weights make several MSTs possible. Any test that expects one specific tree will fail on some inputs.
Checklist
- Sort the edges by weight before Kruskal. Decide how equal weights are ordered, and keep that rule.
- Skip an edge whose two ends are already in one group.
- Check that Kruskal took exactly n - 1 edges. If not, the graph is disconnected.
- Use
long longfor totals and weights. - In Prim, skip a popped vertex that is already in the tree.
- Say which second-best you mean: a different edge set, or a strictly heavier weight.
- Test every method against a brute force on small graphs with many equal weights, and report the number of graphs tested.
Summary
Kruskal and Prim both follow the cut property, one edge at a time. Kruskal grows many small groups and merges them. Prim grows one tree from one vertex. The second-best tree and the membership checks reuse the same tree, with a path query for the swap. Whatever the method, a brute force on small random graphs catches most mistakes that look right by reading.
Practice problems
Practice 1: total by hand
Graph on four vertices with these edges: 0-1 (weight 5), 1-2 (weight 1), 2-3 (weight 4), 0-3 (weight 2), 0-2 (weight 3). Find the MST weight and list the tree edges.
Hint: sort the edges first, then apply Kruskal's rule.
Show the answer
Sorted: 1-2 (1), 0-3 (2), 0-2 (3), 2-3 (4), 0-1 (5). Take 1-2, then 0-3, then 0-2 (it joins with ). Now all four vertices are in one group, so the tree is complete. MST weight: 1 + 2 + 3 = 6. Tree edges: 1-2, 0-3, 0-2. Skipped: 2-3 and 0-1, because their ends are already connected.
Practice 2: edges in some MST and in every MST
For the graph in Practice 1, list the edges that are in some MST, and the edges that are in every MST.
Hint: for "some", ask whether the ends are connected by strictly lighter edges. For "every", ask whether the ends are connected by the other edges of weight at most w.
Show the answer
In some MST: 1-2, 0-3 and 0-2. For 2-3 (weight 4), the lighter edges 1-2, 0-3 and 0-2 connect vertex 2 to vertex 3 through 0, so 2-3 is in no MST. For 0-1 (weight 5), the lighter edges connect 0 and 1 through 2, so 0-1 is in no MST.
In every MST: the same three edges. For 0-2 (weight 3), the other edges of weight at most 3 are 1-2 and 0-3, which leave 0 and 2 apart, so 0-2 is in every MST. The MST is unique.
Practice 3: second-best weight
For the graph in Practice 1, find the weight of the second-best spanning tree (a tree whose edge set differs from the MST).
Hint: for each edge outside the tree, find the heaviest tree edge on its path, then compute total + w(e) - that edge's weight.
Show the answer
The only non-tree edges are 2-3 (weight 4) and 0-1 (weight 5).
- 2-3: the tree path 2-0-3 uses 0-2 (weight 3) and 0-3 (weight 2). The heaviest is 3. Value: 6 + 4 - 3 = 7.
- 0-1: the tree path 0-2-1 uses 0-2 (weight 3) and 1-2 (weight 1). The heaviest is 3. Value: 6 + 5 - 3 = 8.
The smallest value is 7. The tree with 1-2, 0-3 and 2-3 has weight 1 + 2 + 4 = 7.
Practice 4: a triangle of equal weights
A triangle has three vertices and three edges, all of weight 1. Which edges are in some MST, and which are in every MST?
Hint: any two of the three edges form a spanning tree. Apply the two rules to one edge at a time.
Show the answer
Every edge is in some MST, because any two edges form an MST of weight 2. No edge is in every MST, because each MST leaves one edge out. For example, for edge 0-1: no edge is strictly lighter, so it is in some MST. The other two edges, 1-2 and 0-2, connect 0 and 1 through vertex 2, so it is not in every MST.
Practice 5: is the MST unique? (code)
Write a function that returns true when the MST is unique. Use the header in this lesson, and test it on the random graphs from the stress test.
Hint: the MST is unique when no non-tree edge can be swapped in with the same weight. Use second_best_mst, and compare it with the MST total from kruskal.
Show the answer
bool mst_is_unique(int n, const vector<Edge>& edges) {
long long total = kruskal(n, edges);
if (total < 0) return false; // not connected: no spanning tree at all
long long second = second_best_mst(n, edges);
return second == -1 || second > total;
}If the second-best value equals the MST total, a swap gives another tree of the same weight, so the MST is not unique. If the second-best value is larger, no swap keeps the weight, so the MST is unique. If there is no second tree at all, the answer is -1, and the MST is the only spanning tree. This rule depends on the single-swap rule, which we checked against brute force on random graphs, and the same checks passed for this function's rule on 2961 connected graphs with seed 999.