com.mhhe.clrs2e
Class Prim

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

All Implemented Interfaces:

MST

public class Prim

extends java.lang.Object

implements MST

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

Nested Class Summary

private static class

Prim.PrimInfo Inner class to maintain the Vertex object, key, parent, and handle into the priority queue for each vertex.

Constructor Summary

Prim()

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

Prim

public Prim()

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.