Problem Statement
In graph theory, a minimum spanning tree (MST) of a weighted undirected graph is a subset of the edges that connects all the vertices together, without any cycles, and with the minimum possible total edge weight. Given a graph defined by n vertices numbered from 0 to n-1 and a list of its edges, each described as [ai, bi, weighti] representing a weighted, bidirectional edge between nodes ai and bi, the challenge is to identify the critical and pseudo-critical edges in its MST.
- A critical edge in an MST is an edge that, if removed, would increase the total weight of the MST or disconnect the graph.
- A pseudo-critical edge might not appear in all MSTs but is included in at least one MST.
The aim is to return two lists:
- The first list contains indices of edges that are critical.
- The second list contains indices of edges that are pseudo-critical.
The order of indices in the output lists does not matter.
Examples
Example 1
Input:
n = 5, edges = [[0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,4,3],[3,4,3],[1,4,6]]
Output:
[[0,1],[2,3,4,5]]
Explanation:
The figure above describes the graph. The following figure shows all the possible MSTs: Notice that the two edges 0 and 1 appear in all MSTs, therefore they are critical edges, so we return them in the first list of the output. The edges 2, 3, 4, and 5 are only part of some MSTs, therefore they are considered pseudo-critical edges. We add them to the second list of the output.
Example 2
Input:
n = 4, edges = [[0,1,1],[1,2,1],[2,3,1],[0,3,1]]
Output:
[[],[0,1,2,3]]
Explanation:
We can observe that since all 4 edges have equal weight, choosing any 3 edges from the given 4 will yield an MST. Therefore all 4 edges are pseudo-critical.
Constraints
2 <= n <= 1001 <= edges.length <= min(200, n * (n - 1) / 2)edges[i].length == 30 <= ai < bi < n1 <= weighti <= 1000- All pairs
(ai, bi)are distinct.
Approach and Intuition
To solve the problem of finding critical and pseudo-critical edges in an MST, we can adopt the following steps:
Use Kruskal's algorithm to find the initial MST of the given graph and its total weight. This involves:
- Sorting all edges based on their weight.
- Iterating through sorted edges and using a union-find data structure to include edges in the MST unless doing so would form a cycle.
Identify critical edges:
- For each edge in the initial MST, temporarily remove it and calculate the MST's total weight without that edge. An edge is critical if the total weight without it is greater than the original MST's weight or if not all vertices can be connected.
Identify pseudo-critical edges:
- For each edge not in the initial MST, first force its inclusion and then compute the MST's total weight. If this forced inclusion does not result in a higher total weight than the original MST, then the edge is pseudo-critical.
Given the definitions and the process:
- A critical edge is indispensable for any MST with the lowest possible weight. If it's removed, no other MST can match the lowest weight of the original MST.
- A pseudo-critical edge holds potential to be in some, but not necessarily all, MSTs that tie for the lowest weight.
To efficiently implement these steps, always ensure:
- Utilize a union-find (disjoint-set) data structure to manage the cycle checks and sets of connectivity amongst vertices.
- For each edge considered as critical or pseudo-critical, perform a full MST calculation (either excluding the edge or forcing its inclusion and calculating the resultant MST) to definitively determine the effects on the MST's overall weight.
In terms of constraints, namely the limit on n and number of edges, the outlined approach with Kruskal's algorithm (which fundamentally works in O(E log E) due to sorting of edges) fits well within reasonable execution time for the upper bounds provided.
Solutions
- C++
- Java
- Python
class Solution {
public:
class DisjointSet {
public:
vector<int> leader;
vector<int> rank;
int largestComponentSize;
DisjointSet(int n) {
leader.resize(n);
rank.resize(n, 1);
largestComponentSize = 1;
for (int i = 0; i < n; i++) {
leader[i] = i;
}
}
int getLeader(int x) {
if (x != leader[x]) {
leader[x] = getLeader(leader[x]);
}
return leader[x];
}
bool merge(int x, int y) {
int rootX = getLeader(x);
int rootY = getLeader(y);
if (rootX != rootY) {
if (rank[rootX] < rank[rootY]) {
swap(rootX, rootY);
}
leader[rootY] = rootX;
rank[rootX] += rank[rootY];
largestComponentSize = max(largestComponentSize, rank[rootX]);
return true;
}
return false;
}
};
vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges) {
vector<vector<int>> indexedEdges = edges;
int edgeCount = indexedEdges.size();
for (int i = 0; i < edgeCount; i++) {
indexedEdges[i].push_back(i);
}
sort(indexedEdges.begin(), indexedEdges.end(), [](const vector<int>& a, const vector<int>& b) {
return a[2] < b[2];
});
DisjointSet uf(n);
int mstWeight = 0;
for (const auto& edge : indexedEdges) {
if (uf.merge(edge[0], edge[1])) {
mstWeight += edge[2];
}
}
vector<vector<int>> criticalEdges(2);
for (int i = 0; i < edgeCount; i++) {
DisjointSet ufIgnore(n);
int weightWithoutEdge = 0;
for (int j = 0; j < edgeCount; j++) {
if (i != j && ufIgnore.merge(indexedEdges[j][0], indexedEdges[j][1])) {
weightWithoutEdge += indexedEdges[j][2];
}
}
if (ufIgnore.largestComponentSize < n || weightWithoutEdge > mstWeight) {
criticalEdges[0].push_back(indexedEdges[i][3]);
} else {
DisjointSet ufInclude(n);
ufInclude.merge(indexedEdges[i][0], indexedEdges[i][1]);
int weightWithEdge = indexedEdges[i][2];
for (int j = 0; j < edgeCount; j++) {
if (i != j && ufInclude.merge(indexedEdges[j][0], indexedEdges[j][1])) {
weightWithEdge += indexedEdges[j][2];
}
}
if (weightWithEdge == mstWeight) {
criticalEdges[1].push_back(indexedEdges[i][3]);
}
}
}
return criticalEdges;
}
};
The provided C++ code defines an approach to solve the problem of identifying critical and pseudo-critical edges in a Minimum Spanning Tree (MST). This solution utilizes a class DisjointSet that employs the union-find algorithm to manage and merge different sets and to help in determining the MST of a graph.
Design of
DisjointSet:- Leader array represents the parent of each node.
- Rank array represents the size of each component rooted at a particular node.
- Methods in
DisjointSet:getLeader(int x)- Finds and returns the representative (or root) of the set which has node x.merge(int x, int y)- Merges the sets containing x and y. Returnstrueif the merge happened,falseotherwise.
Function
findCriticalAndPseudoCriticalEdges:- Input:
n- Number of vertices.edges- A list of edges where each edge is represented as{u, v, weight}.
- Process:
- Adds the index of each edge to the edge itself for easy identification later.
- Sorts the edges based on their weights to facilitate the Kruskal's algorithm.
- Initializes the original MST weight using union-find on all edges.
- Identifies critical edges by trying to form MST excluding one edge at a time, then checks if the total weight changes or if all nodes are still connected.
- Identifies pseudo-critical edges by forcing one edge into the MST and then trying to form the rest of the MST, checking if the total weight remains the same as the original MST weight.
- Input:
Output:
- Returns a vector of two vectors:
- The first sub-vector contains indices of critical edges.
- The second sub-vector contains indices of pseudo-critical edges.
- Returns a vector of two vectors:
This solution efficiently determines the type of each edge (critical or pseudo-critical) concerning the MST using the union-find method which helps in maintaining and merging the connected components of the graph dynamically. Additionally, the algorithm also defines a comparison method to sort the edges, which is crucial for the proper function of Kruskal's approach used in identifying MSTs.
class Solution {
public List<List<Integer>> computeEdges(int n, int[][] edges) {
int edgeCount = edges.length;
int[][] indexedEdges = new int[edgeCount][4];
for (int i = 0; i < edgeCount; i++) {
System.arraycopy(edges[i], 0, indexedEdges[i], 0, 3);
indexedEdges[i][3] = i;
}
Arrays.sort(indexedEdges, Comparator.comparingInt(edge -> edge[2]));
DisjointSet unionFind = new DisjointSet(n);
int mstCost = 0;
for (int[] edge : indexedEdges) {
if (unionFind.link(edge[0], edge[1])) {
mstCost += edge[2];
}
}
List<List<Integer>> criticalEdgesList = new ArrayList<>();
for (int i = 0; i < 2; i++) {
criticalEdgesList.add(new ArrayList<>());
}
for (int i = 0; i < edgeCount; i++) {
DisjointSet ignoreSet = new DisjointSet(n);
int costWithoutEdge = 0;
for (int j = 0; j < edgeCount; j++) {
if (i != j && ignoreSet.link(indexedEdges[j][0], indexedEdges[j][1])) {
costWithoutEdge += indexedEdges[j][2];
}
}
if (ignoreSet.maxRank < n || costWithoutEdge > mstCost) {
criticalEdgesList.get(0).add(indexedEdges[i][3]);
} else {
DisjointSet forcedSet = new DisjointSet(n);
forcedSet.link(indexedEdges[i][0], indexedEdges[i][1]);
int costWithEdge = indexedEdges[i][2];
for (int j = 0; j < edgeCount; j++) {
if (i != j && forcedSet.link(indexedEdges[j][0], indexedEdges[j][1])) {
costWithEdge += indexedEdges[j][2];
}
}
if (costWithEdge == mstCost) {
criticalEdgesList.get(1).add(indexedEdges[i][3]);
}
}
}
return criticalEdgesList;
}
class DisjointSet {
int[] leader;
int[] rank;
int maxRank;
public DisjointSet(int n) {
leader = new int[n];
rank = new int[n];
maxRank = 1;
for (int i = 0; i < n; i++) {
leader[i] = i;
rank[i] = 1;
}
}
public int find(int x) {
if (x != leader[x]) {
leader[x] = find(leader[x]);
}
return leader[x];
}
public boolean link(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
if (rank[rootX] < rank[rootY]) {
int tmp = rootX;
rootX = rootY;
rootY = tmp;
}
leader[rootY] = rootX;
rank[rootX] += rank[rootY];
maxRank = Math.max(maxRank, rank[rootX]);
return true;
}
return false;
}
}
}
The given Java solution focuses on identifying critical and pseudo-critical edges in a minimum spanning tree (MST) for a graph defined by vertex count n and an edge list edges. Here's how the solution works:
It initializes an array
indexedEdgeswhere each edge has an additional field to keep track of the original index in the input list.Sorts
indexedEdgesby the weight of the edges to facilitate the process of building the MST using Kruskal's algorithm.Utilizes a custom Disjoint Set (union-find) structure,
DisjointSet, to manage the connectivity of vertices during the MST construction. It contains methods for path compression (find) and union by rank (link).Calculates the initial MST cost by iterating through the sorted edges and linking vertices together in increasing order of weight, summing up the weights of edges that contribute to the MST.
Establishes two lists within
criticalEdgesListto separately keep track of critical and pseudo-critical edges.Iterates through each edge and attempts to construct the MST without that edge. If the resulting MST cost is higher than the original, or if not all vertices are connected, the edge is marked as critical.
For each edge not identified as critical, tries to include the edge explicitly and calculates the MST cost. If this forced inclusion does not change the MST cost, the edge is identified as pseudo-critical.
Through this approach, the method computeEdges returns a list containing the indices of critical and pseudo-critical edges from the original input list, providing useful insights into edge roles within the minimum spanning tree structure of the graph.
class Solution:
class DisjointSet:
def __init__(self, size):
self.leader = list(range(size))
self.rank = [1] * size
self.largest_set = 1
def locate(self, node):
if node != self.leader[node]:
self.leader[node] = self.locate(self.leader[node])
return self.leader[node]
def merge(self, node1, node2):
root1 = self.locate(node1)
root2 = self.locate(node2)
if root1 != root2:
if self.rank[root1] < self.rank[root2]:
root1, root2 = root2, root1
self.leader[root2] = root1
self.rank[root1] += self.rank[root2]
self.largest_set = max(self.largest_set, self.rank[root1])
return True
return False
def analyzeEdges(self, vertices, input_edges):
indexed_edges = [edge[:] for edge in input_edges]
for index, edge in enumerate(indexed_edges):
edge.append(index)
indexed_edges.sort(key=lambda e: e[2]) # Sort by weight
uf_base = self.DisjointSet(vertices)
base_mst_weight = 0
for u, v, w, _ in indexed_edges:
if uf_base.merge(u, v):
base_mst_weight += w
critical_edges = []
semi_critical_edges = []
for (u, v, w, edge_index) in indexed_edges:
uf_exclusion = self.DisjointSet(vertices)
excluded_weight = 0
for (x, y, weight, index) in indexed_edges:
if index != edge_index and uf_exclusion.merge(x, y):
excluded_weight += weight
if uf_exclusion.largest_set < vertices or excluded_weight > base_mst_weight:
critical_edges.append(edge_index)
continue
uf_inclusion = self.DisjointSet(vertices)
included_weight = w
uf_inclusion.merge(u, v)
for (x, y, weight, index) in indexed_edges:
if index != edge_index and uf_inclusion.merge(x, y):
included_weight += weight
if included_weight == base_mst_weight:
semi_critical_edges.append(edge_index)
return [critical_edges, semi_critical_edges]
The provided Python solution focuses on the problem of detecting critical and pseudo-critical edges within a Minimum Spanning Tree (MST) of a graph. Here's a breakdown of the solution approach:
DisjointSet Class: A nested class represents a Union-Find data structure. It supports operations to find the representative of a set (using path compression) and to merge two sets. The class also tracks the size of the largest set formed, which is crucial for verifying if all nodes remain connected when considering edge exclusions.
Sorting and Initialization:
- The main function
analyzeEdgesbegins by appending original indices to the edges and sorting them by weight, facilitating the MST construction. - A base MST is computed using all edges to set a weight benchmark.
- The main function
Edge Analysis for Criticality:
- For each edge, the algorithm simulates two scenarios:
- Exclusion scenario: Build an MST without the current edge and compare its weight and connectivity to the base MST. If the exclusion results in a disconnected graph or a heavier MST, the edge is critical.
- Inclusion scenario: Build an MST starting with the current edge. If this results in an MST of weight equal to the base MST, the edge is pseudo-critical.
- The Union-Find structure is used efficiently in both scenarios to manage and compare different sets resulting from edge inclusions or exclusions.
- For each edge, the algorithm simulates two scenarios:
Results Compilation:
- The function returns two lists: one contains indices of critical edges, and the other contains indices of semi-critical (pseudo-critical) edges, based on whether they can be excluded or included, respectively.
This approach leverages the Disjoint Set data structure for efficient graph manipulations, crucial when dealing with MST problems. It uses computational geometry concepts (minimum spanning trees) and a detailed analysis of edge properties. The method ensures all operations respect the size and connectivity constraints, which is critical in many applications, such as network design and circuit layout optimization.
No comments yet.