|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES All Classes | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectde.jstacs.algorithms.graphs.UnionFind
public class UnionFind
This class implements an Union-Find-algorithm with path contraction.
Constructor Summary | |
---|---|
UnionFind(int size)
Creates a new Union-Find data structure with size nodes. |
Method Summary | |
---|---|
int |
find(int n)
Finds the root of the tree with node n and does path
contraction. |
int[][] |
getComponents()
Returns the connected components of the graph. |
boolean |
union(int k1,
int k2)
This method unions the tree that includes the node k1 with
the tree that includes node k2 . |
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Constructor Detail |
---|
public UnionFind(int size)
size
nodes.
size
- the number of nodesMethod Detail |
---|
public int[][] getComponents()
public int find(int n)
n
and does path
contraction. The implemented path contraction is strict, that means it
hooks every node on the way to the root directly to the root.
n
- the node
n
public boolean union(int k1, int k2)
k1
with
the tree that includes node k2
. If both nodes are already in
the same tree nothing is done.
k1
- one nodek2
- another node
true
if a real union is done, false
if
nothing is done
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES All Classes | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |