fork download
copy 
  1. # Helper class for Union-Find (Disjoint Set) for Kruskal's Algorithm
  2. class DisjointSet:
  3.     def __init__(self, n):
  4.         self.parent = list(range(n))
  5.         self.rank = [0] * n
  6.  
  7.     def find(self, u):
  8.         if self.parent[u] != u:
  9.             self.parent[u] = self.find(self.parent[u])  # Path compression
  10.         return self.parent[u]
  11.  
  12.     def union(self, u, v):
  13.         rootU = self.find(u)
  14.         rootV = self.find(v)
  15.         if rootU == rootV:
  16.             return False  # Already connected
  17.         # Union by rank
  18.         if self.rank[rootU] < self.rank[rootV]:
  19.             self.parent[rootU] = rootV
  20.         elif self.rank[rootU] > self.rank[rootV]:
  21.             self.parent[rootV] = rootU
  22.         else:
  23.             self.parent[rootV] = rootU
  24.             self.rank[rootU] += 1
  25.         return True
  26.  
  27. # ✅ Function to compute Minimum Spanning Tree
  28. def spanTree(V, edges):
  29.     # Step 1: Sort edges by weight
  30.     edges.sort(key=lambda x: x[2])
  31.     ds = DisjointSet(V)
  32.  
  33.     mst_weight = 0
  34.     mst_edges = []
  35.  
  36.     # Step 2: Iterate over sorted edges and build MST
  37.     for u, v, weight in edges:
  38.         if ds.union(u, v):
  39.             mst_edges.append((u, v, weight))
  40.             mst_weight += weight
  41.  
  42.     return mst_weight, mst_edges
  43.  
  44. # ✅ Test Cases to verify correctness
  45. def test_spanTree():
  46.     print("Running Test Cases for spanTree...\n")
  47.  
  48.     # Test Case 1: Simple triangle graph
  49.     V1 = 3
  50.     edges1 = [(0, 1, 1), (1, 2, 2), (0, 2, 3)]
  51.     weight1, mst1 = spanTree(V1, edges1)
  52.     print("Test Case 1:")
  53.     print("Expected Weight: 3")
  54.     print("Actual Weight:", weight1)
  55.     print("MST Edges:", mst1, "\n")
  56.  
  57.     # Test Case 2: Disconnected graph
  58.     V2 = 4
  59.     edges2 = [(0, 1, 1), (2, 3, 2)]
  60.     weight2, mst2 = spanTree(V2, edges2)
  61.     print("Test Case 2:")
  62.     print("Expected Weight: 3 (Partial MST)")
  63.     print("Actual Weight:", weight2)
  64.     print("MST Edges:", mst2, "\n")
  65.  
  66.     # Test Case 3: All edges same weight
  67.     V3 = 4
  68.     edges3 = [(0, 1, 5), (1, 2, 5), (2, 3, 5), (3, 0, 5)]
  69.     weight3, mst3 = spanTree(V3, edges3)
  70.     print("Test Case 3:")
  71.     print("Expected Weight: 15")
  72.     print("Actual Weight:", weight3)
  73.     print("MST Edges:", mst3, "\n")
  74.  
  75.     # Test Case 4: Sample example with clear MST
  76.     V4 = 4
  77.     edges4 = [(0, 1, 10), (0, 2, 6), (0, 3, 5), (1, 3, 15), (2, 3, 4)]
  78.     weight4, mst4 = spanTree(V4, edges4)
  79.     print("Test Case 4:")
  80.     print("Expected Weight: 19")
  81.     print("Actual Weight:", weight4)
  82.     print("MST Edges:", mst4, "\n")
  83.  
  84.     # Test Case 5: Fully connected small graph
  85.     V5 = 5
  86.     edges5 = [(i, j, i + j) for i in range(V5) for j in range(i+1, V5)]
  87.     weight5, mst5 = spanTree(V5, edges5)
  88.     print("Test Case 5:")
  89.     print("MST Weight:", weight5)
  90.     print("MST Edges:", mst5, "\n")
  91.  
  92. # ✅ Run Tests
  93. test_spanTree()
  94.  
Success #stdin #stdout 0.08s 14180KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Running Test Cases for spanTree...

Test Case 1:
Expected Weight: 3
Actual Weight: 3
MST Edges: [(0, 1, 1), (1, 2, 2)] 

Test Case 2:
Expected Weight: 3 (Partial MST)
Actual Weight: 3
MST Edges: [(0, 1, 1), (2, 3, 2)] 

Test Case 3:
Expected Weight: 15
Actual Weight: 15
MST Edges: [(0, 1, 5), (1, 2, 5), (2, 3, 5)] 

Test Case 4:
Expected Weight: 19
Actual Weight: 19
MST Edges: [(2, 3, 4), (0, 3, 5), (0, 1, 10)] 

Test Case 5:
MST Weight: 10
MST Edges: [(0, 1, 1), (0, 2, 2), (0, 3, 3), (0, 4, 4)]
https://ideone.com/I499Ob
language:
Python 3 (python  3.12)
created:
5 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!