Class Connectivity<V>
- Type Parameters:
V- the vertex type. Must implementequalsandhashCode.
Internally, this class delegates to an immutable Scala
AbstractDisjointSet instance, swapping the reference on each
mutating operation. From a Java caller's perspective the object behaves
as an ordinary mutable data structure.
Two implementations are available via the factory methods:
createLazy(List)— Weighted Quick Union, O(log n) per operation.createOptimized(List)— Weighted Quick Union with path compression, amortized near-O(1) per operation.
For most purposes createOptimized is the better choice; createLazy
is provided so students can observe the effect of path compression directly. The names
match the Scala layer's Connectivity.createLazy and createOptimized,
which these delegate to; "lazy" here means without path compression, not lazily
evaluated.
Usage example:
Connectivity<String> c = Connectivity.createOptimized(List.of("A", "B", "C", "D"));
c.connect("A", "B");
c.connect("C", "D");
c.isConnected("A", "B"); // true
c.isConnected("A", "C"); // false
c.size(); // 2 (two components)
-
Method Summary
Modifier and TypeMethodDescriptionvoidMerges the components containingv1andv2.static <V> Connectivity<V> createLazy(List<V> vs) Creates aConnectivityusing Weighted Quick Union (O(log n)).static <V> Connectivity<V> createLazy(V... vs) Convenience overload accepting varargs.static <V> Connectivity<V> createOptimized(List<V> vs) Creates aConnectivityusing Weighted Quick Union with path compression (amortized near-O(1)).static <V> Connectivity<V> createOptimized(V... vs) Convenience overload accepting varargs, using path compression.getComponent(V key) Returns the representative (root) of the component containingkey.booleanisConnected(V v1, V v2) Returnstrueifv1andv2belong to the same component.voidAddskeyas a new singleton component.intsize()Returns the number of disjoint components (not the number of vertices).toString()Returns a human-readable summary of thisConnectivity.
-
Method Details
-
createLazy
Creates aConnectivityusing Weighted Quick Union (O(log n)).- Type Parameters:
V- the vertex type.- Parameters:
vs- the initial vertices, each placed in its own singleton component.- Returns:
- a new
Connectivitywithout path compression, containing every vertex ofvs.
-
createOptimized
Creates aConnectivityusing Weighted Quick Union with path compression (amortized near-O(1)).- Type Parameters:
V- the vertex type.- Parameters:
vs- the initial vertices, each placed in its own singleton component.- Returns:
- a new
Connectivitywith path compression, containing every vertex ofvs.
-
createLazy
Convenience overload accepting varargs.- Type Parameters:
V- the vertex type.- Parameters:
vs- the initial vertices.- Returns:
- a new
Connectivitywithout path compression, containing every vertex ofvs.
-
createOptimized
Convenience overload accepting varargs, using path compression.- Type Parameters:
V- the vertex type.- Parameters:
vs- the initial vertices.- Returns:
- a new
Connectivitywith path compression, containing every vertex ofvs.
-
connect
Merges the components containingv1andv2.After this call,
isConnected(v1, v2)returnstrue. Ifv1andv2are already in the same component, this method has no effect.- Parameters:
v1- the first vertex.v2- the second vertex.
-
put
Addskeyas a new singleton component.If
keyis already present, this method has no effect.- Parameters:
key- the vertex to add.
-
isConnected
Returnstrueifv1andv2belong to the same component.- Parameters:
v1- the first vertex.v2- the second vertex.- Returns:
trueif connected,falseotherwise.
-
size
public int size()Returns the number of disjoint components (not the number of vertices).- Returns:
- the component count.
-
getComponent
Returns the representative (root) of the component containingkey.Two vertices are in the same component if and only if their roots are equal.
- Parameters:
key- a vertex.- Returns:
- the root of
key's component.
-
toString
Returns a human-readable summary of thisConnectivity.
-