Datová struktura disjoint-set slouží k vytvoření systému navzájem se nepřekrývajících podmnožin. Pro implementaci se používají dvě základní operace - Union (spojení dvou podmnožin v jednu) a Find (nalezení reprezentanta daného prvku). Sloučením názvů těchto operací vzniká označení pro implementaci této datové struktury - Union-Find problém/Union-Find algoritmus.
Motivace
Union-Find problém nalézá uplatnění při řešení otázky, zda-li jsou dva uzly v té samé komponentě souvislosti grafu G, čehož se využívá například v Kruskalově algoritmu hledání minimální kostry.
Princip a implementace
Řešení problému spočívá v udržováni tzv. reprezentantů komponent, což jsou uzly, kterými všechny uzly z daných komponent prokazují svojí příslušnost. Za předpokladu, že mají dva uzly stejného reprezentanta, tak patří do stejné komponenty.
K reprezentaci se obvykle používá n-ární strom, ve kterém je kořen reprezentantem. Za předpokladu, že spojujeme dvě komponenty (operace Union), tak kratší podstrom zavěsíme pod reprezentanta delšího podstromu, v případě rovnosti délek na volbě nezáleží. Pokud vyhledáváme reprezentata komponenty, tak z daného uzlu vystoupáme do kořenu stromu, což je hledaný reprezentant (operace Find).
Kontrakce cesty
Optimalizací tohoto algoritmu je na závěr operace Find procházené uzly zavěsit přímo pod reprezentanta (zkrátit cestu). Tímto se sice složitost této operace zhorší, ale tento horší případ proběhne pouze jednou, při každém dalším hledání operace proběhne rychleji, než by proběhla bez tohoto vylepšení. Operace nyní proběhnou s amortizovanou složitostí , kde
je inverzní Ackermanova funkce.
Kód
/**
* Disjoint set - Union-Find
* @author Pavel Micka
*/
public class DisjointSet<ENTITY> {
private Node[] nodes;
/**
* Konstruktor (Make-Set)
* @param values hodnoty jednotlivych reprezentantu - id == poradi v seznamu
*/
public DisjointSet(List<ENTITY> values) {
nodes = new Node[values.size()];
for (int i = 0; i < values.size(); i++) {
nodes[i] = new Node<ENTITY>();
nodes[i].id = i;
nodes[i].setValue(values.get(i));
}
}
/**
* Spoji komponenty s danymi id
* (union by rank)
* @param a id 1
* @param b id 2
* @return id reprezentanda spojene komponenty
*/
public int union(int a, int b) {
Node repA = nodes[find(a).id];
Node repB = nodes[find(b).id];
if (repA.getId() == repB.getId()) return repA.getId();
if(repA.rank == repB.rank){
repB.parent = repA;
repA.rank++;
return repA.id;
} else if(repA.rank > repB.rank){
repB.parent = repA;
return repA.id;
} else {
repA.parent = repB;
return repB.id;
}
}
/**
* Vrati reprezentanta komponenty obsahujici uzel s danym id
* @param a id uzlu
* @return reprezentant
*/
public Node find(int a) {
Node n = nodes[a];
int jumps = 0;
while (n.parent != null) {
n = n.parent;
jumps++;
}
if (jumps > 1) repair(a, n.getId());
return n;
}
/**
* Kontrahuje cestu do reprezentanta
* @param a id uzlu, ze ktereho bude cesta opravena
* @param rootId id reprezentanta
*/
private void repair(int a, int rootId) {
Node curr = nodes[a];
while (curr.getId() != rootId) {
Node tmp = curr.parent;
curr.parent = nodes[rootId];
curr = tmp;
}
}
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
for (int i = 0; i < nodes.length; i++) {
builder.append(find(i) + " ");
}
return builder.toString();
}
/**
* Uzel n-arniho stromu
*/
public static class Node<ENTITY> {
/**
* Rank of the tree
*/
private int rank;
private Node parent;
private int id;
private ENTITY value;
/**
* @return the id
*/
public int getId() {
return id;
}
/**
* @return the value
*/
public ENTITY getValue() {
return value;
}
/**
* @param value the value to set
*/
public void setValue(ENTITY value) {
this.value = value;
}
}
}