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

Constructors

Constructor and Description
UnionFind(int size) Creates a new Union-Find data structure with size nodes.

Method Summary

Modifier and Type	Method and Description
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

UnionFind

public UnionFind(int size)

Creates a new Union-Find data structure 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 the 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 of 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