Grokking Graph Algorithms for Coding Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Solution: Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Problem Statement

Given a weighted undirected graph with n vertices numbered from 0 to n-1, and an array edges where edges[i] = [a, b, weight] represents a bidirectional and weighted edge between nodes a and b.

A minimum spanning tree (MST) is a subset of the graph's edges that connects all vertices without cycles and with the smallest possible total edge weight.

An edge is critical if removing it would cause the MST's total weight to increase. An edge is pseudo-critical if it can be part of some MSTs but is not required in all MSTs.

Return a 2D array containing all the critical and pseudo-critical edges in the graph's MST.

Examples

Example 1

  • Input: n = 4, edges = [[0, 1, 1], [1, 2, 2], [2, 3, 3], [0, 3, 4], [1, 3, 5]]
  • Expected Output: [[0,1,2],[]]
Image
  • Justification: Edges [0, 1, 2] are critical as their removal increases the MST weight.

Example 2

  • Input: n = 4, edges = [[0, 1, 1], [1, 2, 1], [2, 3, 1], [0, 3, 1], [0, 2, 2]]
  • Expected Output: [[],[0,1,2,3]]
Image
  • Justification: Edges [0, 1, 2, 3] are pseudo-critical as they exists in some of MSTs.

Example 3

  • Input: n = 6, edges = [[0, 1, 2], [1, 2, 3], [2, 3, 1], [3, 4, 4], [4, 5, 5], [0, 5, 6], [1, 4, 2]]
  • Expected Output: [[0,1,2,4,6],[]]
  • Justification: Edges [0,1,2,4,6] are critical as their removal increases the MST weight.

Constraints:

  • 2 <= n <= 100
  • 1 <= edges.length <= min(200, n * (n - 1) / 2)
  • edges[i].length == 3
  • 0 <= a<sub>i</sub> < b<sub>i</sub> < n
  • 1 <= weight<sub>i</sub> <= 1000
  • All pairs (a<sub>i</sub>, b<sub>i</sub>) are distinct.

Solution

To solve this problem, we need to find the minimum spanning tree (MST) of the graph using Kruskal's algorithm. This algorithm sorts the edges by weight and adds them to the MST, ensuring no cycles are formed until all vertices are connected. The first step is to determine the MST's total weight without removing any edges. Next, for each edge, we test its removal to check if the MST weight increases, indicating a critical edge. For pseudo-critical edges, we force their inclusion in the MST and check if the resulting tree's weight matches the original MST's weight.

This approach ensures we correctly identify all critical and pseudo-critical edges. By using Kruskal's algorithm, we efficiently handle edge weights and connectivity checks. This method is effective because it leverages the union-find data structure to detect cycles, ensuring optimal performance.

Step-by-Step Algorithm

  1. Initialize Indexed Edges:

    • Create a new list of edges where each edge is appended with its original index.

  2. Sort Edges:

    • Sort the edges by their weight in ascending order.

  3. Calculate MST Weight:

    • Use the Union-Find data structure to find the Minimum Spanning Tree (MST) and calculate its total weight.
    • Initialize Union-Find with nodes and set standardWeight to 0.
    • Iterate over sorted edges and use connect to check if the edge can be added without forming a cycle. If yes, add the edge's weight to standardWeight.

  4. Check for Critical and Pseudo-Critical Edges:

    • Initialize the result list with two empty lists for critical and pseudo-critical edges.

  5. Check Each Edge:

    • For each edge:
      • Ignore the Edge:
        • Create a new Union-Find instance and ignore the current edge.
        • Calculate the MST weight without the current edge.
        • If the graph is disconnected or the MST weight increases, the edge is critical. Add it to the critical edges list.
      • Force the Edge:
        • Create a new Union-Find instance and force the current edge.
        • Calculate the MST weight including the current edge.
        • If the MST weight remains the same, the edge is pseudo-critical. Add it to the pseudo-critical edges list.

  6. Return Result:

    • Return the list containing critical and pseudo-critical edges.

Algorithm Walkthrough

Input:

n = 4
edges = [[0, 1, 1], [1, 2, 2], [2, 3, 3], [0, 3, 4], [1, 3, 5]]

  1. Initialize Indexed Edges:

    • indexedEdges = [[0, 1, 1, 0], [1, 2, 2, 1], [2, 3, 3, 2], [0, 3, 4, 3], [1, 3, 5, 4]]

  2. Sort Edges:

    • indexedEdges after sorting by weight: [[0, 1, 1, 0], [1, 2, 2, 1], [2, 3, 3, 2], [0, 3, 4, 3], [1, 3, 5, 4]]

  3. Calculate MST Weight:

    • Initialize Union-Find for 4 nodes.
    • standardWeight = 0
    • Add edge [0, 1, 1, 0] to MST. standardWeight = 1
    • Add edge [1, 2, 2, 1] to MST. standardWeight = 3
    • Add edge [2, 3, 3, 2] to MST. standardWeight = 6
    • Edges [0, 3, 4, 3] and [1, 3, 5, 4] form cycles, not added.

  4. Check for Critical and Pseudo-Critical Edges:

    • Initialize result: result = [[], []]

  5. Check Each Edge:

    • Edge [0, 1, 1, 0]:

      • Ignore the Edge:
        • Initialize Union-Find.
        • MST without [0, 1, 1, 0]:
          • Add edge [1, 2, 2, 1]. MST weight = 2.
          • Add edge [2, 3, 3, 2]. MST weight = 5.
          • Add edge [0, 3, 4, 3]. MST weight = 9.
          • Graph remains connected.
        • Since MST weight > standardWeight, [0, 1, 1, 0] is critical. result[0] = [0]
      • Force the Edge:
        • Initialize Union-Find.
        • MST with [0, 1, 1, 0]:
          • Add edge [0, 1, 1, 0]. MST weight = 1.
          • Add edge [1, 2, 2, 1]. MST weight = 3.
          • Add edge [2, 3, 3, 2]. MST weight = 6.
          • MST weight equals standardWeight, so not pseudo-critical.

    • Edge [1, 2, 2, 1]:

      • Ignore the Edge:
        • Initialize Union-Find.
        • MST without [1, 2, 2, 1]:
          • Add edge [0, 1, 1, 0]. MST weight = 1.
          • Add edge [2, 3, 3, 2]. MST weight = 4.
          • Add edge [0, 3, 4, 3]. MST weight = 8.
          • Graph remains connected.
        • Since MST weight > standardWeight, [1, 2, 2, 1] is critical. result[0] = [0, 1]
      • Force the Edge:
        • Initialize Union-Find.
        • MST with [1, 2, 2, 1]:
          • Add edge [1, 2, 2, 1]. MST weight = 2.
          • Add edge [0, 1, 1, 0]. MST weight = 3.
          • Add edge [2, 3, 3, 2]. MST weight = 6.
          • MST weight equals standardWeight, so not pseudo-critical.

    • Edge [2, 3, 3, 2]:

      • Ignore the Edge:
        • Initialize Union-Find.
        • MST without [2, 3, 3, 2]:
          • Add edge [0, 1, 1, 0]. MST weight = 1.
          • Add edge [1, 2, 2, 1]. MST weight = 3.
          • Add edge [0, 3, 4, 3]. MST weight = 7.
          • Graph remains connected.
        • Since MST weight > standardWeight, [2, 3, 3, 2] is critical. result[0] = [0, 1, 2]
      • Force the Edge:
        • Initialize Union-Find.
        • MST with [2, 3, 3, 2]:
          • Add edge [2, 3, 3, 2]. MST weight = 3.
          • Add edge [0, 1, 1, 0]. MST weight = 4.
          • Add edge [1, 2, 2, 1]. MST weight = 6.
          • MST weight equals standardWeight, so not pseudo-critical.

    • Edge [0, 3, 4, 3]:

      • Ignore the Edge:
        • Initialize Union-Find.
        • MST without [0, 3, 4, 3]:
          • Add edge [0, 1, 1, 0]. MST weight = 1.
          • Add edge [1, 2, 2, 1]. MST weight = 3.
          • Add edge [2, 3, 3, 2]. MST weight = 6.
          • MST weight equals standardWeight.
        • Since MST weight equals standardWeight, [0, 3, 4, 3] is not critical.
      • Force the Edge:
        • Initialize Union-Find.
        • MST with [0, 3, 4, 3]:
          • Add edge [0, 3, 4, 3]. MST weight = 4.
          • Add edge [0, 1, 1, 0]. MST weight = 5.
          • Add edge [1, 2, 2, 1]. MST weight = 7.
          • MST weight > standardWeight, so not pseudo-critical.

    • Edge [1, 3, 5, 4]:

      • Ignore the Edge:
        • Initialize Union-Find.
        • MST without [1, 3, 5, 4]:
          • Add edge [0, 1, 1, 0]. MST weight = 1.
          • Add edge [1, 2, 2, 1]. MST weight = 3.
          • Add edge [2, 3, 3, 2]. MST weight = 6.
          • MST weight equals standardWeight.
        • Since MST weight equals standardWeight, [1, 3, 5, 4] is not critical.
      • Force the Edge:
        • Initialize Union-Find.
        • MST with [1, 3, 5, 4]:
          • Add edge [1, 3, 5, 4]. MST weight = 5.
          • Add edge [0, 1, 1, 0]. MST weight = 6.
          • Add edge [1, 2, 2, 1]. MST weight = 8.
          • MST weight > standardWeight, so not pseudo-critical.

  6. Return Result:

    • Return result = [[0, 1, 2], []].

Code

Python3
Python3
. . . .

Complexity Analysis

Time Complexity

  1. Sorting the Edges: Sorting the edges based on their weights takes O(E \log E), where (E) is the number of edges.
  2. Union-Find Operations:
    • Union and Find Operations: Each union or find operation takes nearly constant time, O(\alpha(N)), where \alpha is the Inverse Ackermann function, which grows very slowly. Therefore, for (E) edges, the total time for union-find operations is O(E \alpha(N)).
    • Iterating Through Edges for Critical and Pseudo-Critical Edges: We iterate through each edge and perform union-find operations for each edge, which is O(E^2 \alpha(N)).

Combining these, the overall time complexity is O(E \log E + E^2 \alpha(N)), which simplifies to O(E^2 \alpha(N)).

Space Complexity

  1. Storage for Union-Find Data Structures: We maintain multiple union-find data structures, each taking O(N) space.
  2. Storage for Indexed Edges: We maintain a list of indexed edges, taking O(E) space.
  3. Result Storage: The result list takes O(E) space.

Combining these, the overall space complexity is O(N + E).

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible