Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree
Understanding the Problem
We have a weighted undirected graph and we need to classify every edge into one of three categories: critical (must be in every MST), pseudo-critical (appears in some but not all MSTs), or neither (never appears in any MST).
A critical edge is one whose removal would either disconnect the graph or force a higher MST weight. If removing an edge makes it impossible to connect all vertices, or if the cheapest spanning tree without that edge costs more than the original MST, then that edge is critical.
A pseudo-critical edge is harder to detect. It is not critical (so at least one MST exists without it), but it does appear in at least one valid MST. To test this, force-include the edge and then build the rest of the MST around it. If the total weight still equals the original MST weight, that edge can participate in some MST.
Both tests rely on the same building block: Kruskal's algorithm with a Union-Find data structure to compute MST weights. We compute a baseline MST weight once, then test each edge by either excluding it or force-including it and comparing the result against the baseline.
Key Constraints:
2 <= n <= 100-> Very small vertex count. Even O(n^2) per edge or O(E * E) overall is fine.1 <= edges.length <= min(200, n * (n - 1) / 2)-> At most 200 edges. We can afford to run a full MST computation for each edge (200 MST computations, each O(E * alpha(n))).1 <= weight_i <= 1000-> With at most 200 edges, the total MST weight is at most 199 * 1000 < 200,000, which fits in a 32-bit int. No overflow handling is needed.
Approach 1: Brute Force (Enumerate All MSTs)
Intuition
The definitions translate directly into a procedure: generate every possible spanning tree, keep the ones with minimum weight, then check which edges appear in all of those MSTs (critical) versus only some of them (pseudo-critical).
For a graph with E edges and n vertices, a spanning tree uses exactly n-1 edges. We enumerate all C(E, n-1) combinations of edges, check whether each forms a spanning tree, and if so, track its total weight. After finding the minimum weight, we classify edges by which MSTs they appear in.
This is correct but combinatorially explosive. With E = 200 and n = 100, C(200, 99) is astronomically large. Even for moderate inputs the number of combinations grows past anything we can iterate over.
Algorithm
- Generate all combinations of n-1 edges from the edge list.
- For each combination, check if it forms a spanning tree (connects all vertices with no cycles).
- Track the minimum total weight across all valid spanning trees.
- For each edge, check if it appears in all minimum spanning trees (critical) or in at least one (pseudo-critical).
Visualization and Code
Loading animation...
- Time Complexity: O(C(E, n-1) n alpha(n)). We enumerate all C(E, n-1) combinations of edges, and for each combination we run Union-Find operations on n-1 edges. C(E, n-1) can be astronomically large, making this impractical for most inputs.
- Space Complexity: O(C(E, n-1) * n). Storing all valid MSTs. In the worst case, this is enormous.
This approach finds the answer but enumerates an exponential number of edge subsets. The next approach avoids enumeration entirely by classifying each edge with at most two MST computations.
Approach 2: Kruskal's with Edge Testing (Union-Find)
Intuition
Instead of finding all MSTs and then checking membership, we classify each edge with two tests:
- Critical test: Remove the edge and compute the MST of the remaining graph. If the MST weight increases (or the graph becomes disconnected), the edge is critical.
- Pseudo-critical test: Force-include the edge (union its endpoints first), then build the rest of the MST using Kruskal's. If the total weight equals the original MST weight, the edge belongs to at least one valid MST.
First compute the baseline MST weight. Then for each edge, run the exclusion test. If the weight goes up, the edge is critical. If not, run the inclusion test, and if that weight matches the baseline, the edge is pseudo-critical. An edge that fails both tests never appears in any MST and is left out of both lists.
The exclusion test detects critical edges. A critical edge is one that appears in every MST, so removing it from the graph must raise the minimum achievable spanning-tree weight above the baseline. If the graph becomes disconnected without the edge, the edge was a bridge, and a bridge is in every spanning tree, so it is critical too. Both outcomes are captured by "weight without the edge > baseline" because a disconnected build returns infinity.
The inclusion test detects pseudo-critical edges constructively. Forcing the edge in and completing the tree with Kruskal's produces the cheapest spanning tree that contains that edge. If that cost equals the baseline, the result is itself a valid MST containing the edge, which proves the edge belongs to at least one MST. Running the inclusion test only after the exclusion test fails guarantees the edge is not also critical, so it is correctly placed in the pseudo-critical group.
Algorithm
- Store the original index of each edge (we need to return indices, but Kruskal's requires sorting by weight).
- Sort the edges by weight.
- Compute the baseline MST weight using standard Kruskal's algorithm.
- For each edge
i: - Exclusion test: Run Kruskal's without edge
i. If the resulting weight > baseline or the graph is disconnected, edgeiis critical. - Inclusion test (only if not critical): Force-include edge
ifirst, then run Kruskal's on the remaining edges. If the total weight equals the baseline, edgeiis pseudo-critical. - Return the two lists of edge indices.
Visualization and Code
Loading animation...
- Time Complexity: O(E^2 alpha(n)). We run Kruskal's algorithm (which is O(E alpha(n)) with sorted edges) once for the baseline and up to 2E times for the edge tests. Sorting is O(E log E), which is dominated by the E iterations.
- Space Complexity: O(n + E). The Union-Find structure uses O(n) space, and we store the indexed edges in O(E) space. We rebuild the Union-Find from scratch for each test, so no cumulative space is needed.