com.mhhe.clrs2e
Class Kruskal

java.lang.Object
  |
  +--com.mhhe.clrs2e.Kruskal

All Implemented Interfaces:

MST

public class Kruskal

extends java.lang.Object

implements MST

Implements Kruskal's algorithm for minimum spanning tree from page 569 of Introduction to Algorithms, Second edition.

Nested Class Summary

private static class

Kruskal.WeightedEdge Inner class for weighted edges so that the edges can be sorted and considered in nondecreasing order by weight.

Constructor Summary

Kruskal()

Method Summary

com.mhhe.clrs2e.WeightedAdjacencyListGraph

computeMST(com.mhhe.clrs2e.WeightedAdjacencyListGraph g) Computes the minimum spanning tree of a weighted, undirected graph.

Methods inherited from class java.lang.Object

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

Constructor Detail

Kruskal

public Kruskal()

Method Detail

computeMST

public com.mhhe.clrs2e.WeightedAdjacencyListGraph computeMST(com.mhhe.clrs2e.WeightedAdjacencyListGraph g)

Computes the minimum spanning tree of a weighted, undirected graph.

Specified by:

computeMST in interface MST

Parameters:

g - The undirected graph.

Returns:

The subgraph of g that is a minimum spanning tree.