Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

## de.jstacs.algorithms.graphs
Class UnionFind

    java.lang.Object
      de.jstacs.algorithms.graphs.UnionFind

    public class UnionFind

extends Object

This class implements an Union-Find-algorithm with path contraction.

Author:
  Jens Keilwagen

Constructor Summary
`UnionFind(int size)` Creates a new Union-Find-datastructure with `size` nodes.

Method Summary
`int` | `find(int n)` Finds the root of 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

### UnionFind

    public UnionFind(int size)

  Creates a new Union-Find-datastructure with `size` nodes.

  Parameters:
    `size` - the number of nodes

Method Detail

### getComponents

    public int[][] getComponents()

  Returns the connected components of the graph.

  Returns:
    the connected components of the graph

### find

    public int find(int n)

  Finds the root of tree with node `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.

  Parameters:
    `n` - the node
  Returns:
    the root for the tree with node `n`

### union

    public boolean union(int k1,
                         int k2)

  This method unions the tree that includes the node `k1` with the tree that includes node `k2`. If both nodes are already in the same tree nothing is done.

  Parameters:
    `k1` - one node
    `k2` - another node
  Returns:
    `true` if a real union is done, `false` if nothing is done.

Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD