de.jstacs.algorithms.graphs
Class MST

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

public class MST
extends Object

This class enables you to compute the maximal spanning forest for an undirected, weighted graph. If a weight is Double.NEGATIVE_INFINITY the edge will not be used.

Author:

Jens Keilwagen

Constructor Summary

MST()

Method Summary

static int[][]

kruskal(double[][] weights) Does Kruskals algorithm and finds the maximal spanning tree (MST).

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

MST

public MST()

Method Detail

kruskal

public static int[][] kruskal(double[][] weights)

Does Kruskals algorithm and finds the maximal spanning tree (MST).

Parameters:

weights - the matrix of weights, weights.length is the number of nodes in the tree, weights[i][j] is the weight for edge (i,i+j)

Returns:

the MST of the weighted graph