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

Constructors

Constructor and Description
MST()

Method Summary

Methods

Modifier and Type	Method and Description
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+1), e.g., weights[0][0] is the weight for edge (0,1).

Returns:

the MST of the weighted graph, where each row of the array contains one edge [i, j] without any specific order.