Critical and pseudo-critical MST edges

Why this matters

A company connects its offices with cables. Each possible cable has a price. The company wants every office reachable from every other office, at the lowest total price. The cheapest set of cables that does this is called a minimum spanning tree (MST). A planner asks two follow-up questions about it.

• Which cables are essential? If one of them is removed from the plan, the total price goes up or the network splits in two.
• Which cables could be swapped in or out without changing the price? These cables are optional in the sense that some cheapest plan uses them and some other cheapest plan does not.

This lesson builds a program that answers both questions. It uses Kruskal's algorithm, a method for finding an MST by sorting edges and adding them one at a time. The lesson on Prim's algorithm versus Kruskal's compares Kruskal with another method. Here we use only the version of Kruskal that this problem needs.

Vocabulary before code

• Node: a point in the network, such as an office. Nodes are numbered from 0 to n minus 1 in the code.
• Edge: a link between two nodes, such as a cable. Each edge has a weight, which is its price.
• Undirected: an edge goes both ways. A cable between office 0 and office 1 can carry data either way. We store each edge once.
• Spanning tree: a set of edges that connects every node, with no loops. A tree on n nodes always has exactly n minus 1 edges.
• Cycle: a path that starts and ends at the same node, with no repeated edge. If a new edge closes a cycle, adding it creates a loop, so it is not allowed in a tree.
• Minimum spanning tree (MST): a spanning tree whose total weight is the smallest possible. A network can have more than one MST when two or more trees have the same lowest total.
• Critical edge: an edge that is in every MST. If it is removed, the lowest total weight goes up, or no spanning tree is left at all.
• Pseudo-critical edge: an edge that is in some MST but not in every MST. It can be used in a cheapest plan, but it is not required.
• Kruskal's algorithm: sort the edges from cheapest to most expensive. Walk through the list and add each edge that joins two parts of the network that were not joined before. Skip any edge that would close a cycle.
• Disjoint set: a structure that keeps track of which nodes are already joined. It can answer "are these two nodes already connected?" and join two groups. This is the same union-find idea used in the other lessons of this module.

Start with a small network

Take four towns, numbered 0 to 3. Here are the cables with their prices.

• Cable A joins towns 0 and 1 and costs 1.
• Cable B joins towns 1 and 2 and costs 1.
• Cable C joins towns 2 and 3 and costs 2.
• Cable D joins towns 0 and 3 and costs 2.

The cheapest plan uses three cables, because four towns need three links. Sorted by price, the cables are A (1), B (1), C (2) and D (2). Kruskal adds A, then B, then C. The total is 1 + 1 + 2 = 4. When it reaches D, D would close a loop through towns 0, 1, 2 and 3, so it is skipped. The MST weight is 4.

Now ask the planner's questions. Is cable A essential? If A is removed, the cheapest plan has to use D instead. Without A, the cables B (1), C (2) and D (2) connect the towns for a total of 1 + 2 + 2 = 5. The total went up from 4 to 5, so A is critical.

Is cable D essential? If D is removed, the plan A, B, C still connects everything for a total of 4. The total did not change, so D is not critical. Can D be used in a cheapest plan anyway? Yes. Force D into the plan first. Then the cheapest way to finish is to add A and B, which costs 2 + 1 + 1 = 4. The total is still 4, so D is pseudo-critical.

That is the whole task in miniature. For each edge, compute the MST weight without it and with it forced in. The rest of the lesson makes this exact and shows how to do it with code.

The idea in plain words

Picture a set of rail tracks between cities. The planner has a budget and wants the cheapest set of tracks that keeps all cities connected. Each track has a fixed cost.

To test one track, there are two experiments.

1. Take the track out of the catalogue and find the cheapest network without it. If the cheapest network is more expensive, or the cities cannot all be connected, the track is critical.
2. Force the track into the network first and find the cheapest network that includes it. If the cheapest network with the track still costs the same as the best overall, the track is pseudo-critical. If it costs more, the track is in neither group.

Both experiments reuse Kruskal's algorithm, with one small change each time. The first experiment skips one edge. The second experiment starts with one edge already chosen.

The result is a single comparison for each edge. The base weight best is the MST weight of the full network. For edge i:

• If the weight without i is larger than best, or the cities are no longer connected, edge i is critical.
• Otherwise, if the weight with i forced in equals best, edge i is pseudo-critical.
• Otherwise, edge i is in neither group.

Kruskal's algorithm with two switches

The program needs one function that runs Kruskal's algorithm and can be told to skip one edge or to take one edge first. Here is how each part works.

The function receives the number of nodes, the list of edges, and an order list. The order list holds edge indices sorted from the cheapest edge to the most expensive. We sort once, at the start, and reuse the order in every run. The sorting is a single step at the start.

The function receives two extra numbers: banned and forced. A value of -1 means "not used". If banned is an edge index, the run skips that edge. If forced is an edge index, the run adds that edge first, before anything else.

If the number of edges added is less than n minus 1, the nodes are not all connected, and the function returns -1. A value of -1 is never a real weight, because all weights in this lesson are zero or positive.

The code below shows the complete program. It was compiled with g++ -std=c++20 -Wall and run. The first three functions are the edge struct, the disjoint set, and the Kruskal run.

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
 
struct Edge {
    int a;
    int b;
    int weight;
};
 
class DisjointSet {
public:
    explicit DisjointSet(int n) : parent_(n), size_(n, 1) {
        for (int i = 0; i < n; ++i) parent_[i] = i;
    }
    int find(int x) {
        while (parent_[x] != x) {
            parent_[x] = parent_[parent_[x]];
            x = parent_[x];
        }
        return x;
    }
    bool unite(int a, int b) {
        int ra = find(a);
        int rb = find(b);
        if (ra == rb) return false;
        if (size_[ra] < size_[rb]) std::swap(ra, rb);
        parent_[rb] = ra;
        size_[ra] += size_[rb];
        return true;
    }
 
private:
    std::vector<int> parent_;
    std::vector<int> size_;
};
 
// Kruskal's algorithm. `order` lists edge indices from lightest to heaviest.
// `banned` is an edge index to skip (-1 for none).
// `forced` is an edge index to take first (-1 for none).
// Returns the total weight, or -1 when the edges do not connect all n nodes.
long long mstWeight(int n, const std::vector<Edge>& edges,
                    const std::vector<int>& order, int banned, int forced) {
    DisjointSet dsu(n);
    long long total = 0;
    int used = 0;
 
    if (forced >= 0) {
        const Edge& e = edges[forced];
        dsu.unite(e.a, e.b);
        total += e.weight;
        ++used;
    }
    for (int i : order) {
        if (i == banned || i == forced) continue;
        const Edge& e = edges[i];
        if (dsu.unite(e.a, e.b)) {
            total += e.weight;
            ++used;
        }
    }
    return used == n - 1 ? total : -1;
}

The long long type holds the total. A plain int is usually 32 bits, and a sum of many large prices can pass its limit of about 2.1 billion. Using long long avoids that on common systems.

In the forced run, dsu.unite is called on the forced edge before the loop. The loop then skips that same edge with i == forced. Skipping it is not strictly needed, because unite would return false for the second copy. The explicit check makes the intent clear.

The main function: test every edge

The next part of the program loops over every edge and applies the two experiments.

struct Answer {
    std::vector<int> critical;
    std::vector<int> pseudo;
};
 
Answer findCriticalAndPseudoCritical(int n, const std::vector<std::vector<int>>& raw) {
    std::vector<Edge> edges;
    for (const auto& row : raw) edges.push_back(Edge{row[0], row[1], row[2]});
 
    std::vector<int> order(edges.size());
    std::iota(order.begin(), order.end(), 0);
    std::stable_sort(order.begin(), order.end(), [&](int x, int y) {
        return edges[x].weight < edges[y].weight;
    });
 
    long long best = mstWeight(n, edges, order, -1, -1);
    Answer answer;
 
    for (int i = 0; i < static_cast<int>(edges.size()); ++i) {
        long long without = mstWeight(n, edges, order, i, -1);
        if (without == -1 || without > best) {
            answer.critical.push_back(i);
            continue;
        }
        long long with = mstWeight(n, edges, order, -1, i);
        if (with == best) answer.pseudo.push_back(i);
    }
    return answer;
}

The order list is made by std::iota, which fills a list with 0, 1, 2 and so on. Then std::stable_sort puts the indices in order of weight. The word stable means that edges with equal weight keep their input order. That keeps the result predictable.

The first check inside the loop is the critical test. The without == -1 case is the disconnected case. If removing edge i leaves the nodes unconnected, the edge is critical, even though the code stores the result as -1 and not as a large number. The second check is the pseudo-critical test. It only runs when the edge is not critical.

Each edge is added to critical or pseudo by its index in the input list. The loop goes from 0 upward, so both lists come out in input order.

The rest of the program prints each result as one pair of lists, such as [[0,1],[2,3,4,5]], with no spaces.

void printList(const std::vector<int>& v) {
    std::cout << '[';
    for (std::size_t i = 0; i < v.size(); ++i) {
        if (i > 0) std::cout << ',';
        std::cout << v[i];
    }
    std::cout << ']';
}
 
void show(int n, const std::vector<std::vector<int>>& edges) {
    Answer ans = findCriticalAndPseudoCritical(n, edges);
    std::cout << "[";
    printList(ans.critical);
    std::cout << ",";
    printList(ans.pseudo);
    std::cout << "]\n";
}
 
int main() {
    show(5, {{0, 1, 1}, {1, 2, 1}, {2, 3, 2}, {0, 3, 2}, {0, 4, 3}, {3, 4, 3}, {1, 4, 6}});
    show(4, {{0, 1, 1}, {1, 2, 1}, {2, 3, 1}, {0, 3, 1}});
    show(3, {{0, 1, 1}, {1, 2, 2}, {0, 2, 3}});
    show(3, {{0, 1, 1}, {1, 2, 1}});
}

Each input row has three numbers: the two nodes and the weight. The index of a row in the list is the edge's identity, so the output refers to rows by position.

Here is the output of the program.

[[0,1],[2,3,4,5]]
[[],[0,1,2,3]]
[[0,1],[]]
[[0,1],[]]

The first line is the output for the first network. The second line has no critical edges, and every edge is pseudo-critical. The third and fourth lines each have two critical edges. The third network has one edge that is in neither group, which is discussed below.

Worked example 1: the five-node network

The first network has five nodes and seven edges. Here is the table of edges.

Kruskal runs on the full set first. It adds edges 0, 1, 2 and then 4, skipping edge 3 because it would close a loop. The total is 1 + 1 + 2 + 3 = 7, so best is 7.

The table below shows the two experiments for each edge.

Let us check two rows by hand.

Edge 0 is critical. Without it, Kruskal adds edges 1, 2, 3 and 4 in that order. Edge 1 joins 1 and 2. Edge 2 joins 2 and 3. Edge 3 joins 0 and 3, which is the first edge that reaches node 0. Edge 4 (0-4) comes next and reaches node 4, so it is added, and edge 5 (3-4) is then skipped because node 4 is already joined. The total is 1 + 2 + 2 + 3 = 8. Since 8 is larger than 7, edge 0 is critical.

Edge 6 is in neither group. Without it, the network still costs 7, so it is not critical. When forced in, edge 6 costs 6 first. Adding the cheapest edges that finish the tree gives 6 + 1 + 1 + 2 = 10. That is more than 7, so edge 6 is not pseudo-critical.

The program's output for this network is [[0,1],[2,3,4,5]]. It agrees with the table: critical edges 0 and 1, pseudo-critical edges 2, 3, 4 and 5, and nothing for edge 6.

Worked example 2: a loop of four equal edges

Now take a square with four towns and four cables, all priced at 1. The cables are 0-1, 1-2, 2-3 and 0-3.

The full network costs best = 3, because three cables are needed. Remove any one cable. The other three still form a path that connects all four towns, and that path costs 3. Nothing gets more expensive, so no edge is critical.

Force any one cable in. The forced cable costs 1, and Kruskal then adds two more cables of cost 1 each. The total is 3 again, so every edge is pseudo-critical.

This example shows why the output list is not always one-sided. When all weights are equal, many different trees are cheapest, and each edge appears in some of them.

Worked example 3: an edge that belongs to neither group

The third network is a triangle with weights 1, 2 and 3. The edges are 0-1 (weight 1), 1-2 (weight 2) and 0-2 (weight 3).

The MST uses the two cheapest edges, which gives best = 3.

Edge 2 is the most expensive edge in the triangle. Without it, the cheapest tree is still 3, so it is not critical. But when it is forced in, the tree must also use edge 0, and the total becomes 3 + 1 = 4. That is more than 3, so edge 2 is in neither group. The program prints [[0,1],[]].

This is the case the second check guards against. An edge can be non-critical and still be useless to a cheapest tree.

Common mistakes

Treating a disconnected network as a normal weight

If removing an edge leaves the nodes unconnected, mstWeight returns -1. That value is smaller than best, so a check written as without > best gives the wrong answer. The edge must be marked critical, because the network cannot be finished without it.

We tested this on a path with three nodes, 0 to 1 to 2, where both edges have weight 1. We ran only the first check, with the comparison written as without > best. The program printed:

edge 0: without=-1 best=2 not critical
edge 1: without=-1 best=2 not critical

Both edges are critical, because removing either one disconnects the path. The comparison wrongly reports "not critical". The fix is the explicit without == -1 test in the main loop.

Forgetting to sort before running Kruskal

Kruskal only gives the cheapest tree when it tries edges from the cheapest to the most expensive. The order list must be sorted by weight before any run. If the list is left in input order, the base weight and the forced runs can both be wrong, and an edge can be put in the wrong group.

Listing indices in the wrong order

The problem asks for indices as they appear in the input. The main loop goes from 0 to the last edge, so the lists are filled in input order automatically. If the code loops over the sorted order list instead, the lists come out in weight order, and the answer is wrong.

Calling the function with too few arguments

mstWeight takes five arguments: the node count, the edge list, the order, the banned index and the forced index. A call that leaves out one of them does not compile. We wrote a small test that called mstWeight(3, edges, order, -1) and compiled it with g++ -std=c++20 -Wall. The compiler printed this error:

badcall_mst.cpp: In function ‘int main()’:
badcall_mst.cpp:69:28: error: too few arguments to function ‘long long int mstWeight(int, const std::vector<Edge>&, const std::vector<int>&, int, int)’
   69 |     long long w = mstWeight(3, edges, order, -1);
      |                   ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
badcall_mst.cpp:43:11: note: declared here
   43 | long long mstWeight(int n, const std::vector<Edge>& edges,
      |           ^~~~~~~~~

The message gives the full signature of the function. Compare it with the call to find the missing argument. The file name in the first line is the test file. The badcall_mst.cpp:43 line points at the function's definition.

Practice

Each exercise gives a network or a call. Work out the answer on paper, then check it against the answer below it.

1. Four nodes in a path. The edges are [0,1,4], [1,2,5] and [2,3,6]. Which edges are critical? Give the output of show.

   Show the answer

   All three edges are critical. The network is a tree, so removing any edge splits it into two parts. The output is [[0,1,2],[]].

2. Three nodes in a triangle. All three edges have weight 2: [0,1,2], [1,2,2] and [0,2,2]. What does the program print?

   Show the answer

   The output is [[],[0,1,2]]. The best total is 4, using any two edges. Without any one edge, the other two still total 4, so nothing is critical. Forcing any edge in gives 4 again, so every edge is pseudo-critical.

3. Three nodes with edges [0,1,5], [1,2,1] and [0,2,1]. Which edges are critical, and which are pseudo-critical?

   Show the answer

   The best total is 2, using edges 1 and 2. Edges 1 and 2 are critical, because removing either one forces the total up to 6. Edge 0 is not critical, since without it the total is still 2. Forcing edge 0 in gives 5 + 1 = 6, so edge 0 is in neither group. The output is [[1,2],[]].

4. Path of three edges, all weight 1: edges 0-1, 1-2 and 2-3. Call mstWeight(4, edges, order, -1, 1), which forces edge 1 in and bans nothing. What does it return?

   Show the answer

   It returns 3. Edge 1 (1-2) is added first, then edges 0 (0-1) and 2 (2-3) are added. Each has weight 1, so the total is 3, which is the weight of the full path.

5. Use the five-node network from worked example 1. Call mstWeight(5, edges, order, 4, -1), which bans edge 4 (0-4) and forces nothing. What does it return?

   Show the answer

   It returns 7. Without edge 4, Kruskal adds edges 0, 1 and 2, skips edge 3 because it closes a loop, and then adds edge 5 (3-4, weight 3). The total is 1 + 1 + 2 + 3 = 7.

Summary

• An edge is critical when the cheapest tree gets more expensive, or disconnects, without it.
• An edge is pseudo-critical when forcing it in leaves the cheapest total unchanged.
• Each edge needs at most two extra Kruskal runs: one with the edge banned and, if it is not critical, one with it forced in.
• The sorted order list is built once and reused in every run.
• A disconnected result must be checked on its own, because the code returns -1 for it.