Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree
Hard
Given a weighted undirected connected graph with n vertices numbered from 0 to n - 1, and an array edges where edges[i] = [a_i, b_i, weight_i] represents a bidirectional and weighted edge between nodes a_i and b_i. A minimum spanning tree (MST) is a subset of the graph's edges that connects all vertices without cycles and with the minimum possible total edge weight.
Find all the critical and pseudo-critical edges in the given graph's minimum spanning tree (MST). An MST edge whose deletion from the graph would cause the MST weight to increase is called a critical edge. On the other hand, a pseudo-critical edge is that which can appear in some MSTs but not all.
Example 1:
Consider a graph with 5 vertices and the following edges:
edges = [[0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,4,3],[3,4,3],[1,4,6]]
The critical edges are [0, 1] because they appear in all possible MSTs. The pseudo-critical edges are [2, 3, 4, 5] because they appear in some, but not all, MSTs.
Example 2:
Consider a graph with 4 vertices and the following edges:
edges = [[0,1,1],[1,2,1],[2,3,1],[0,3,1]]
In this case, all edges [0, 1, 2, 3] are pseudo-critical because any 3 edges can form an MST.
Your task is to write a function that takes the number of vertices n and the list of edges edges as input and returns a list containing two lists: the first list contains the indices of the critical edges, and the second list contains the indices of the pseudo-critical edges. The order of indices in the output lists does not matter.
Solution
Finding Critical and Pseudo-Critical Edges in a Minimum Spanning Tree
This problem asks us to identify critical and pseudo-critical edges within a graph's minimum spanning tree (MST). A critical edge is one that, if removed, would increase the weight of the MST. A pseudo-critical edge is one that can be part of some MSTs but not all.
1. Naive (Brute Force) Solution
The most straightforward approach is to iterate through each edge and check its criticality and pseudo-criticality.
- Calculate the MST weight: Initially, compute the MST weight of the original graph using Kruskal's or Prim's algorithm.
- Check for critical edges: For each edge, temporarily remove it from the graph and recalculate the MST weight. If the new MST weight is greater than the original MST weight, the removed edge is critical.
- Check for pseudo-critical edges: For each non-critical edge, force it to be included in the MST and recalculate the MST weight. If the new MST weight is the same as the original, then the edge is pseudo-critical.
Code (Python)
def find_critical_and_pseudo_critical_edges_naive(n, edges):
def calculate_mst_weight(included_edge=None, excluded_edge=None):
# Kruskal's algorithm with optional inclusion/exclusion
parent = list(range(n))
rank = [0] * n
def find(i):
if parent[i] == i:
return i
parent[i] = find(parent[i])
return parent[i]
def union(i, j):
root_i = find(i)
root_j = find(j)
if root_i != root_j:
if rank[root_i] < rank[root_j]:
parent[root_i] = root_j
elif rank[root_i] > rank[root_j]:
parent[root_j] = root_i
else:
parent[root_j] = root_i
rank[root_i] += 1
return True
return False
mst_weight = 0
num_edges = 0
sorted_edges = sorted([(w, u, v, idx) for idx, (u, v, w) in enumerate(edges)])
if included_edge is not None:
w, u, v, idx = included_edge
if union(u, v):
mst_weight += w
num_edges += 1
for w, u, v, idx in sorted_edges:
if excluded_edge is not None and idx == excluded_edge[3]:
continue
if union(u, v):
mst_weight += w
num_edges += 1
if num_edges != n - 1:
return float('inf') # Graph not connected
return mst_weight
original_mst_weight = calculate_mst_weight()
critical_edges = []
pseudo_critical_edges = []
for idx, (u, v, w) in enumerate(edges):
# Check for critical edges
excluded_edge = (w, u, v, idx)
if calculate_mst_weight(excluded_edge=excluded_edge) > original_mst_weight:
critical_edges.append(idx)
else:
# Check for pseudo-critical edges
included_edge = (w, u, v, idx)
if calculate_mst_weight(included_edge=included_edge) == original_mst_weight:
pseudo_critical_edges.append(idx)
return [critical_edges, pseudo_critical_edges]
Time Complexity
O(m * m log n), where m is the number of edges and n is the number of vertices. We iterate through each edge (O(m)) and, for each edge, recalculate the MST (O(m log n)).
Space Complexity
O(n) primarily due to the Union-Find data structure.
2. Optimal Solution
The optimal solution also uses Kruskal's algorithm, but with optimizations to reduce redundant MST calculations.
- Calculate the MST: Calculate the MST of the original graph using Kruskal's algorithm. Store the edges that are part of the MST.
- Check for critical edges: For each edge in the original graph, temporarily exclude it and recalculate the MST. If the new MST weight is greater, the edge is critical.
- Check for pseudo-critical edges: For each edge not marked as critical, force the edge into the MST calculation. This means pre-unioning the vertices connected by the edge before proceeding with Kruskal's. If the resulting MST weight is the same as the original, mark the edge as pseudo-critical.
Code (Python)
def find_critical_and_pseudo_critical_edges(n, edges):
def calculate_mst_weight(must_include=[], must_exclude=None):
parent = list(range(n))
rank = [0] * n
def find(i):
if parent[i] == i:
return i
parent[i] = find(parent[i])
return parent[i]
def union(i, j):
root_i = find(i)
root_j = find(j)
if root_i != root_j:
if rank[root_i] < rank[root_j]:
parent[root_i] = root_j
elif rank[root_i] > rank[root_j]:
parent[root_j] = root_i
else:
parent[root_j] = root_i
rank[root_i] += 1
return True
return False
mst_weight = 0
num_edges = 0
# Include mandatory edges first
for u, v, w, idx in must_include:
if union(u, v):
mst_weight += w
num_edges += 1
sorted_edges = sorted([(w, u, v, idx) for idx, (u, v, w) in enumerate(edges)])
for w, u, v, idx in sorted_edges:
if must_exclude is not None and idx == must_exclude:
continue
if union(u, v):
mst_weight += w
num_edges += 1
# Check if all nodes are connected
num_components = 0
for i in range(n):
if parent[i] == i:
num_components += 1
if num_components > 1:
return float('inf')
return mst_weight
# Calculate the original MST weight and MST edges
original_mst_weight = calculate_mst_weight()
critical_edges = []
pseudo_critical_edges = []
for idx, (u, v, w) in enumerate(edges):
# Check for critical edges
if calculate_mst_weight(must_exclude=idx) > original_mst_weight:
critical_edges.append(idx)
else:
# Check for pseudo-critical edges
must_include = [(u, v, w, idx)]
if calculate_mst_weight(must_include=must_include) == original_mst_weight:
pseudo_critical_edges.append(idx)
return [critical_edges, pseudo_critical_edges]
Time Complexity
O(m * m log n), where m is the number of edges and n is the number of vertices. Although we have optimizations, the fundamental complexity remains the same because we still iterate through each edge and perform Kruskal's algorithm in the worst case.
Space Complexity
O(n) primarily due to the Union-Find data structure.
Edge Cases
- Disconnected Graph: If the input graph is disconnected, the MST weight will be infinite, and you need to handle this case appropriately.
- Multiple MSTs: The problem statement specifies that if an edge can appear in some MSTs but not all, it's pseudo-critical. This requires checking if forcing the edge inclusion results in an MST with the same weight as the original.
- Empty Graph or Invalid Inputs: Handling invalid inputs like empty graphs or graphs with incorrect edge formats is crucial for a robust solution.
Summary
Both the naive and optimized solutions rely on the core idea of recalculating the MST with specific edges either included or excluded. The optimal solution aims to reduce unnecessary calculations, but the time complexity remains similar. Union-Find optimization is used to efficiently check for cycles and calculate MST weight.
