com.codemelon.graph.algorithm.spanningtree

Class Prim<E extends SpanningTreeEdgeData,V extends UndirectedPrimVertex<E>>

java.lang.Object

com.codemelon.graph.algorithm.spanningtree.Prim<E,V>

public class Prim<E extends SpanningTreeEdgeData,V extends UndirectedPrimVertex<E>>
extends java.lang.Object

Implementation of Prim's algorithm for growing a minimum spanning tree. Follows CLRS, pp. 634ff. In this implementation, the markEdges() method does 2 things:

1. Marks the edges belonging to the minimum spanning tree as BLACK and all other edges WHITE, and
2. Specifies the parents of all vertices so that the specified root vertex is the root node in the minimum spanning tree marked by BLACK edges.

Constructor Summary

Constructors

Constructor and Description
Prim(UndirectedWeightedEdgeGraph<E,V> graph)

Method Summary

Methods

Modifier and Type	Method and Description
void	markEdges(V root) Set edges in minimum spanning tree to BLACK, all other edges are set to WHITE.

Methods inherited from class java.lang.Object

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

Constructor Detail

Prim

public Prim(UndirectedWeightedEdgeGraph<E,V> graph)

Method Detail

markEdges

public void markEdges(V root)

Set edges in minimum spanning tree to BLACK, all other edges are set to WHITE. Parents of all vertices in the graph are also modified to show a path leading back to the specified root.

Parameters:

root - source vertex for minimum spanning tree