|
TUM CCSM Commons | |||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectedu.tum.cs.commons.collections.ManagedIntArray
edu.tum.cs.commons.algo.UnionFind
public class UnionFind
Implementation of a simple union find data structure. It implements the "partial path compression" heuristic but does not use "union by rank" but instead uses randomization.
Field Summary |
---|
Fields inherited from class edu.tum.cs.commons.collections.ManagedIntArray |
---|
array, size |
Constructor Summary | |
---|---|
UnionFind()
|
Method Summary | |
---|---|
int |
addElement()
Adds a new element to this union find structure and returns its index. |
protected void |
connectToRepresentative(int element,
int representative)
Connects the given element (must also be representative) to the given representative. |
int |
find(int element)
Finds and returns the representative for the given element. |
void |
union(int element1,
int element2)
Merges the classes in which element1 and element2 are, by giving them the same representative. |
Methods inherited from class edu.tum.cs.commons.collections.ManagedIntArray |
---|
addArrayElement, addArrayElements |
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Constructor Detail |
---|
public UnionFind()
Method Detail |
---|
public int find(int element)
public void union(int element1, int element2)
protected void connectToRepresentative(int element, int representative)
public int addElement()
|
TUM CCSM Commons | |||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |