Disjoint Set Union (DSU / Union-Find) Engine
Maintains disjoint component trees using 32-bit contiguous parent and rank arrays, executing near-constant time O(α(|V|)) Find and Union operations via Path Compression and Union by Rank.
Computer Science / Greedy MST & Disjoint Set Union
FREE TO EXPLORELABORATORY 12 · COMPUTER SCIENCE
Empirical Analysis of Greedy Algorithms: Minimum Spanning Trees (Kruskal's vs. Prim's), Disjoint Set Union (DSU / Union-Find), the Cut Property, and Asymptotic Network Optimization
To investigate the fundamental mechanisms of Greedy Algorithms in network optimization, compare Kruskal's algorithm against Prim's algorithm, evaluate the amortized near-constant time complexity O(α(|V|)) of Disjoint Set Union (DSU) with Path Compression and Union by Rank, and verify the exact linear lookup scaling law Q(|V|) = 2|E| = 8.0000 · |V| lookups across connected networks with candidate edge count |E| = 4|V|. Explore interactive search algorithms, compare operation counts and analyse complexity scaling.
COMPUTE · BENCHMARK · ANALYSE
Your virtual algorithm laboratory.
DISJOINT SET REPRESENTATIVE LOOKUPS Q(|V|)—
EXECUTION STATUS
Ready to execute vertex count benchmark.
Adjust vertex count n, then execute benchmark.
Operation counts are generated deterministically by the exact algorithmic execution model. Modern hardware benchmarks additionally reflect cache line prefetching and branch misprediction penalties.
Algorithmic assumptions and limits
The simulated execution environment models idealized network graphs where memory lookups execute with deterministic cost of 1 operation per DSU Find query (Q(|V|) = 8|V|). In physical microprocessors, execution latency is modulated by CPU L1/L2 data cache hit ratios during parent pointer walking, Translation Lookaside Buffer (TLB) page table walks across large heap buffers, memory bus contention during array sorting, and branch predictor stalls during cycle detection conditionals. In Kruskal's Minimum Spanning Tree algorithm on a connected undirected graph G = (V, E) with |E| = 4|V| candidate edges, every candidate edge (u, v) is inspected exactly once in non-decreasing weight order. To evaluate whether edge (u, v) connects disjoint components or forms a cycle, the algorithm invokes Find(u) and Find(v), executing exactly 2 DSU representative queries per edge. Across all candidate edges, the total number of disjoint set lookups scales strictly as Q(|V|) = 2|E| = 2(4|V|) = 8.0000·|V| lookups with exact theoretical intercept Q_0 = 0.0000 lookups, while producing an optimal tree of exactly |V| - 1 edges.
Computational tools & environment.
Weighted Network Topology & Edge Pool Generator
Synthesizes connected undirected graphs of |V| vertices and |E| = 4|V| edges with positive integer weights w(e) ∈ [1, 100] drawn from a uniform pseudo-random distribution.
Edge Weight Quicksort / Introsort Sorter
Sorts candidate edges in ascending order of edge weight in O(|E| log |E|) time to establish the greedy candidate stream for Kruskal's selection loop.
Min-Heap Priority Queue (Prim's Algorithm)
Maintains tentative crossing edge cut weights for Prim's vertex-growing algorithm, supporting O(log |V|) extract_min and decrease_key operations.
Cycle Detection & Cut Property Validator
Asserts acyclicity of the growing edge subset, verifying that every chosen edge represents the minimum-weight crossing edge across a graph cut.
Telemetry & Inverse Ackermann Complexity Register
Records discrete Find operations, Union operations, rank comparisons, and amortized tree path length compressions during MST construction.
FOLLOW THE METHOD
A reason behind every step.
To investigate the fundamental mechanisms of Greedy Algorithms in network optimization, compare Kruskal's algorithm against Prim's algorithm, evaluate the amortized near-constant time complexity O(α(|V|)) of Disjoint Set Union (DSU) with Path Compression and Union by Rank, and verify the exact linear lookup scaling law Q(|V|) = 2|E| = 8.0000 · |V| lookups across connected networks with candidate edge count |E| = 4|V|. Suggested independent settings: 50, 100, 200, 300, 500, 750, 1000 vertices.
01
Network Synthesis & Connected Component Verification
Generate a connected undirected graph G = (V, E) with |V| vertices and |E| = 4|V| candidate edges with random integer weights w(e) ∈ [1, 100]. Verify network connectivity using a single-pass Breadth-First Search.
02
Disjoint Set Forest Allocation & Sentinel Initialization
Allocate parent array parent[0 .. |V|-1] initialized to self-pointers (parent[i] = i) and rank array rank[0 .. |V|-1] initialized to 0, establishing |V| disjoint singleton components.
03
Candidate Edge Stream Ascending Sort
Sort all |E| = 4|V| edges in non-decreasing weight order using introsort in O(|E| log |E|) time. Initialize the MST edge collector with target size |V| - 1.
04
Greedy Edge Inspection & Cycle Rejection
Iterate through sorted edges (u, v): execute Find(u) and Find(v) to locate component root representatives (incrementing the DSU lookup counter by 2). If roots match, reject edge to prevent cycle formation.
05
Component Union & MST Edge Inclusion
If roots differ, accept edge into the MST and invoke Union(root_u, root_v) using Union by Rank. Increment the accepted edge counter; repeat until exactly |V| - 1 edges are selected.
06
Asymptotic Linear Regression & Complexity Verification
Record total DSU lookups across network sizes |V| ∈ [50, 100, 200, 300, 500, 750, 1000]. Regress lookups Q(|V|) against vertex count |V| to compute slope k_mst, intercept Q_0, and coefficient of determination R².
YOUR NOTEBOOK · 0 OBSERVATIONS
Turn measurements into asymptotic insight.
Points are your recorded benchmark observations. The regression line validates Greedy MST & Disjoint Set Union complexity scaling.
LINEAR ASYMPTOTIC FIT · y = mx + b
Q(|V|) = k_mst · |V| + Q_0 = 8.0000 · |V| + 0.0000 lookups
| # | Network vertex count |V| (|E| = 4|V| candidate edges) (vertices) | Disjoint set representative lookups Q(|V|) (lookups) | Network vertex count |V| (vertices) | Disjoint set lookups Q(|V|) = 2|E| = 8·|V| (lookups) | Remove |
|---|
No readings yet. Execute a vertex count benchmark and record it.
Calculate it yourself.
CHECK YOUR UNDERSTANDING