Critical and pseudo-critical MST edges in Python

Why this matters

Imagine a company that must link five offices with leased cables. Each possible cable has a monthly cost. The company wants every office connected to every other office, and it wants the cheapest total cost. The cheapest set of cables that connects everything, with no loop, is called a minimum spanning tree (MST).

Planners often ask a follow-up question. Which cables are essential? If one essential cable is dropped from the plan, the total cost goes up. Other cables can be swapped out with no change in cost, because another cheap cable does the same job. Knowing which cables fall into each group helps a planner decide where to spend time on negotiation.

This lesson sorts every cable into one of three groups. Some cables must be in every cheapest plan. Some are in at least one cheapest plan but not in all of them. The rest are in no cheapest plan at all. The method uses Kruskal's algorithm, which builds an MST by taking the cheapest cables first, and union-find, which tells whether two offices are already connected. Earlier lessons in this module cover both. This lesson uses Kruskal's algorithm as a tool.

Terms used in this lesson

A vertex is one point in the network. Here a vertex is an office. Vertices are numbered 0 to n minus 1, where n is the number of vertices.

An edge is a link between two vertices. Here an edge is a cable. Each edge in this lesson has two endpoints and a weight, which is its cost. An edge is written [u, v, w]: it links vertex u to vertex v and costs w.

A list is an ordered collection written with square brackets, such as [1, 5, 3]. The first item has index 0. A list of edges is a list of lists, one inner list of three numbers per edge.

The index of an edge is its position in the input list. The first edge has index 0. The answer is given in terms of these indexes, so the input order must be kept even when the code sorts the edges by cost.

A spanning tree is a set of edges that connects every vertex and contains no loop. For n vertices, a spanning tree always has exactly n minus 1 edges. A minimum spanning tree is a spanning tree whose total weight is as small as possible. Some networks have more than one MST, because two edges can have the same weight.

A connected graph is one where you can reach any vertex from any other vertex by following edges. If the network is not connected, no spanning tree exists.

Kruskal's algorithm builds an MST in three steps. Sort the edges by weight, lightest first. Walk through the sorted list. Take an edge if it links two vertices that are not yet connected, and skip it otherwise. Stop when you have n minus 1 edges. A union-find structure answers the question "are these two vertices already connected?" quickly.

A critical edge is an edge that appears in every MST. Equivalently, if you remove it, the cheapest possible total weight goes up, or the network falls apart.

A pseudo-critical edge is an edge that appears in at least one MST but not in every MST. It can be left out of some cheapest plans and included in others.

A neutral edge is an edge that appears in no MST. Some route of cheaper cables already connects its two ends.

The question and the answer format

The input is a number n and a list of edges. The output is a list of two lists of edge indexes. The first inner list holds the critical edges. The second inner list holds the pseudo-critical edges. Every other edge is neutral and appears in neither list.

Here is a small example with 3 vertices and 3 edges:

With three vertices, an MST has two edges. The cheapest plan takes edge 0 (cost 1) and edge 2 (cost 3), for a total of 4. Edge 1 (cost 5) is never needed. Edge 0 and edge 2 are in every MST, so they are critical. Edge 1 is in no MST, so it is neutral. The answer is critical [0, 2] and pseudo-critical [].

The rest of this lesson shows how a program reaches that answer for any input, without checking every possible plan by hand.

The idea: test each edge two ways

Compute the MST weight once. Call it base. Then, for each edge, run two tests.

Test A: remove the edge. Run Kruskal's algorithm again, but skip this edge. There are three possible results.

• The new total equals base. A cheapest plan exists without this edge. The edge is not critical.
• The new total is larger than base. Every cheapest plan needed this edge. The edge is critical.
• No spanning tree can be built without this edge. The edge is a bridge between two halves of the network, so it is critical.

Test B: force the edge in. Run Kruskal's algorithm again, but start with this edge already taken, before any sorting. The edge's weight is added to the total. Then the other edges are added in the usual order.

• If the total equals base, some cheapest plan includes this edge. The edge is pseudo-critical, unless Test A already marked it as critical.
• If the total is larger than base, no cheapest plan includes this edge. The edge is neutral.

Why does this work? If removing the edge keeps the cost at base, the cheapest plan does not need it, so it cannot be in every MST. If forcing the edge in gives base, the cheapest plan can be built around it, so it is in at least one MST. Those two facts split the edges into the three groups.

The order of the tests matters, and a later section shows why.

Worked example 1: the 3 vertex triangle

Use the table from the question section. The edges are 0 (weight 1), 1 (weight 5) and 2 (weight 3). When sorted by weight, the order is edge 0, edge 2, edge 1.

First the base weight. Kruskal takes edge 0, which links vertices 0 and 1. It takes edge 2, which links vertex 2 to them. That is two edges, so the tree is complete. The base is 1 + 3 = 4.

Now the tests for each edge.

Edge 0 (weight 1). Test A: skip edge 0. The sorted order is now edge 2 and edge 1. Edge 2 links 0 and 2. Edge 1 links 1 and 2, so it is taken and joins vertex 1 in. The total is 3 + 5 = 8. That is larger than 4, so edge 0 is critical.

Edge 1 (weight 5). Test A: skip edge 1. Kruskal takes edge 0 (links 0 and 1) and edge 2 (links 0 and 2). The total is 1 + 3 = 4, which equals the base. Edge 1 is not critical. Test B: force edge 1 in first. Its weight 5 is the starting total, and vertices 1 and 2 are now in one group. Edge 0 links vertex 0 to vertex 1, and vertex 0 is still alone, so edge 0 is taken and the total becomes 6. Edge 2 links vertices 0 and 2, which are now in the same group, so it is skipped. The total is 6, which is not 4. Edge 1 is neutral.

Edge 2 (weight 3). Test A: skip edge 2. Kruskal takes edge 0 (links 0 and 1) and edge 1 (links 1 and 2). The total is 1 + 5 = 6. That is larger than 4, so edge 2 is critical.

The final answer is critical [0, 2] and pseudo-critical []. The program prints the same result for this input, as a later section shows.

Worked example 2: a square with equal weights

Now take 4 vertices in a ring with every edge weighing 1. The edges are 0 (0 to 1), 1 (1 to 2), 2 (2 to 3) and 3 (0 to 3).

The base is 3, because any three of the four edges form a spanning tree and each costs 1.

Test A on any one edge leaves the other three edges, which still connect all four vertices. The total is 3, equal to the base, so no edge is critical.

Test B on any one edge takes that edge first, then adds the other edges as needed. Each forced total is 3, equal to the base. So every edge is pseudo-critical.

The answer is critical [] and pseudo-critical [0, 1, 2, 3]. The ring has many MSTs, and every edge belongs to at least one of them.

This example shows why ties make the problem harder. With unequal weights, a single heavy edge can be the only link to a part of the network, and it will be critical. With equal weights, every edge can be swapped for another.

Worked example 3: a network with a mix

The next example has 5 vertices and 7 edges. Each row shows the index, the two endpoints and the weight.

The base MST is 7. Kruskal takes edges 0, 1, 2 and 4, for a total of 1 + 1 + 2 + 3 = 7. It skips edge 3 because vertices 0 and 3 are already connected through 0, 1 and 2.

Running the two tests on each edge gives the Test A total (edge removed, written without) and the Test B total (edge forced in, written forced). Here is the real output for this input:

base 7
edge 0 without=8 forced=7
edge 1 without=8 forced=7
edge 2 without=7 forced=7
edge 3 without=7 forced=7
edge 4 without=7 forced=7
edge 5 without=7 forced=7
edge 6 without=7 forced=10

Read the table row by row.

• Edge 0: removing it gives 8, which is larger than 7. Critical.
• Edge 1: removing it gives 8. Critical.
• Edge 2: removing it gives 7, so it is not critical. Forcing it in gives 7, so it is pseudo-critical.
• Edge 3: removing it gives 7. Forcing it in gives 7. Pseudo-critical.
• Edge 4: removing it gives 7. Forcing it in gives 7. Pseudo-critical.
• Edge 5: removing it gives 7. Forcing it in gives 7. Pseudo-critical.
• Edge 6: removing it gives 7, so it is not critical. Forcing it in gives 10, which is larger than 7. Neutral.

The answer is critical [0, 1] and pseudo-critical [2, 3, 4, 5]. Edge 6 is neutral, because the cable from vertex 1 to vertex 4 costs 6, and the cheaper routes already connect those vertices.

Edge 4 is a good test of the reasoning. Removing it does not raise the cost, because edge 5 (from 3 to 4, weight 3) can do the same job. Forcing it in gives 7 as well, because the rest of the tree can be built around it. So it is in some MST and not in every MST.

The code

The program below does the work for any input. It has one function for the sorted order, one Kruskal function with two optional settings (an edge to skip, and an edge to force in), and a main function that runs the two tests on every edge.

Save it as critical_edges.py and run it with python3 critical_edges.py.

The output is:

[[0, 1], [2, 3, 4, 5]]
[[], [0, 1, 2, 3]]
[[0, 2], []]
base weight of tri: 4
tri without edge 0: 8
tri with edge 1 forced: 6

The first two lines are the first two worked examples. The third line is the triangle from worked example 1. The last three lines print the numbers that worked example 1 computed by hand, so you can match the code to the explanation.

Walking through the helper functions

list(range(n)) builds the list [0, 1, ..., n - 1]. Each vertex starts as its own group, so parent[x] is x at the start. A vertex whose parent entry equals its own index is a root.

find follows parents until it reaches a root. The line parent[x] = parent[parent[x]] is a shortcut called path halving. It points x at its grandparent, so later searches are shorter. union finds both roots and attaches one under the other. It returns True only when the two vertices were in different groups.

Python lists change in place. find and union change the parent list they receive, so each call to mst_weight makes a new list with parent = list(range(n)). Otherwise one test would leave groups behind for the next test.

sorted(range(len(edges)), key=lambda i: edges[i][2]) returns a new list of indexes. The key is a short function that says what to compare. Here it is the weight, which sits at position 2 of each edge. A lambda is a small function with no name. The edges list is not changed, so the original indexes stay correct.

Walking through the Kruskal function

The mst_weight function is the part that runs many times. It takes five inputs. n is the vertex count. edges is the input list. order is the sorted list of edge indexes. skip and forced are the two settings from the two tests.

Each setting has the default None. In Python, None means "no value". The default is not -1 or 0, because index 0 is a real edge. If the default were 0, every call would skip edge 0 by mistake.

The line u, v, w = edges[idx] is called tuple unpacking. It takes the three numbers of one edge and gives each one its own name in a single line.

The function starts every vertex in its own group. It then handles the forced edge, if there is one, by joining its endpoints and adding its weight. After that it walks through the sorted list. It skips the edge named by skip, and it skips the forced edge, which has already been taken. For each other edge, union returns True only when the two endpoints were in different groups. In that case the weight is added and the count of taken edges goes up by 1.

At the end, a spanning tree has exactly n minus 1 taken edges. If the count is smaller, the network could not be connected with the edges that were allowed, and the function returns -1. The last line uses a conditional expression, total if ... else -1, which is Python's short form of an if that returns one of two values.

Why the code tests critical before pseudo-critical

The if in the main loop checks critical first. The elif only runs for edges that are not critical. This order is needed for correctness.

A critical edge is in every MST. So forcing it in always gives base, and the forced test alone would label it as pseudo-critical. Here is the path example, with edges 0 (0 to 1, weight 1) and 1 (1 to 2, weight 1) on three vertices. Running the same two tests on it gives:

path base 2
edge 0 without -1
edge 0 forced 2

The forced test for edge 0 gives 2, which equals the base. If the code checked the forced test first, it would call edge 0 pseudo-critical. The removal test gives -1, which means the network falls apart without edge 0. That makes edge 0 critical. Checking removal first gives the right answer.

Common mistakes

Forgetting the disconnected case

The removal test returns -1 when the network falls apart. A common bug is to compare the result only with base, like this: if without > base:. A -1 is never larger than base, so the edge is missed.

Running a version with only that check on the path example prints:

path, disconnect check missing: [[], [0, 1]]

The correct answer is [[0, 1], []]. Both edges of the path are critical, because removing either one disconnects the network. The buggy version calls them both pseudo-critical. The check without < 0 or in the real code handles this case.

Forgetting to sort the edges

Kruskal's algorithm needs the lightest edges first. If the code uses the input order, it may pick an expensive edge before a cheap one, and it will end up with a tree that costs too much.

On the triangle from worked example 1, the input order is edge 0 (weight 1), edge 1 (weight 5), edge 2 (weight 3). Without sorting, Kruskal takes edge 0 and then edge 1, for a total of 6. The correct base is 4. A version that skips the sort prints:

tri base weight, no sort: 6

The sorted order prints 4. Every later comparison uses base, so one wrong base makes every answer wrong.

Sorting the edges list itself

The sort must not change the order of the edges list. Python has two ways to sort. sorted(edges, ...) returns a new list and leaves the original alone. edges.sort(...) changes the original list in place, so the index of each edge changes.

If the code calls tri.sort(key=lambda e: e[2]) before the search, the answer refers to positions in the new order, not to the edges the caller gave. Running that version prints:

after in-place sort: [[0, 1, 1], [0, 2, 3], [1, 2, 5]]
answer from sorted list: [[0, 1], []]
answer from original list: [[0, 2], []]

The first line shows the list after the in-place sort. The correct answer for the original triangle is [[0, 2], []], and the wrong version returns [[0, 1], []]. The sorted() function avoids this mistake because it leaves the original list alone.

Edges with the wrong number of values

Each edge must have exactly three numbers. If an edge is written with only two numbers, the tuple unpacking line fails. Calling mst_weight(3, [[0, 1], [1, 2]], [0, 1]) raises this error:

ValueError: not enough values to unpack (expected 3, got 2)

The message says what is wrong: the line expected three values and got two. The fix is to give every edge a weight.

Practice

Each exercise is followed by its answer. Try each one on paper before you read the answer.

Exercise 1. Use the triangle with all three edges weighing 2: edge 0 links 0 and 1, edge 1 links 1 and 2, and edge 2 links 0 and 2. Find the critical and pseudo-critical edges.

Show the answer

The base is 4, because any two edges form a spanning tree and each costs 2. Removing any one edge leaves two edges that still connect all three vertices, so the total stays 4, and no edge is critical. Forcing any edge in gives 2 plus one more edge of weight 2, which is 4. So every edge is pseudo-critical. The answer is critical [] and pseudo-critical [0, 1, 2]. The program prints [[], [0, 1, 2]] for this input.

Exercise 2. The input is 4 vertices and two edges: edge 0 links 0 and 1 with weight 1, and edge 1 links 2 and 3 with weight 1. Describe what the program does, and give the exact error it raises.

Show the answer

The base computation is mst_weight with no skip and no forced edge. Kruskal takes both edges, which is 2 edges, but a tree on 4 vertices needs 3. The function returns -1. The check after it sees a negative base and raises an exception. The exception is ValueError with the message graph is not connected. A test program that catches it and prints the error reads:

caught: ValueError: graph is not connected

Exercise 3. Explain in plain words why the program tests removal before forcing an edge in, for each edge that is not critical.

Show the answer

Removal tells the program whether the edge is needed. If the cost stays the same without it, some cheapest plan avoids it. Forcing tells the program whether the edge can be part of a cheapest plan at all. If the cost is still the base after forcing it in, a cheapest plan includes it. An edge that passes the forcing test but fails the removal test is critical, and that is why the critical check comes first.

Exercise 4. Count how many times the program calls mst_weight for a graph with m edges. Give the count as a formula, and then give the count for the 7-edge network in worked example 3.

Show the answer

The program calls mst_weight once for the base. For each edge it makes one removal call. It makes a forced call only when the edge is not critical, so the most calls is 2m plus 1, when no edge is critical. For the 7-edge network in worked example 3, the base call is 1, the removal calls are 7, and the forced calls are 5, because edges 0 and 1 are critical and skip the forced call. The total is 13. Each call does one walk through the sorted edges with union-find, so the total work is about 2m times the cost of one Kruskal run.

Exercise 5. Change the triangle so that edge 1 has weight 2 instead of 5. The edges are now 0 (0 to 1, weight 1), 1 (1 to 2, weight 2) and 2 (0 to 2, weight 3). Find the base, and say which edges are critical.

Show the answer

Sorted, the edges are 0 (weight 1), 1 (weight 2) and 2 (weight 3). Kruskal takes edges 0 and 1, which link all three vertices, so the base is 3. Removing edge 0 leaves edges 1 and 2, with total 5, which is larger than 3, so edge 0 is critical. Removing edge 1 leaves edges 0 and 2, with total 4, which is larger than 3, so edge 1 is critical. Removing edge 2 leaves edges 0 and 1, which is still 3, so edge 2 is not critical. Forcing edge 2 in gives 3 plus edge 0, which makes 4, so edge 2 is neutral. The answer is critical [0, 1] and pseudo-critical []. The program prints [[0, 1], []] for this input.

Summary

• Compute the MST weight once. Every edge is then tested against that number.
• Removing an edge and seeing the cost go up, or the network fall apart, makes the edge critical.
• Forcing an edge in and getting the same cost makes the edge pseudo-critical. Test critical first, because a critical edge also passes the forcing test.
• The sort must keep the original edge indexes. Use sorted() rather than .sort() on the edges list, and handle a disconnected result as a special case.
• The method runs about 2m Kruskal passes for m edges, which is fine for the sizes in this course.