graph
Class MyPrimJarnik
java.lang.Object
graph.MyPrimJarnik
- All Implemented Interfaces:
- MinSpanForest
public class MyPrimJarnik
- extends Object
- implements MinSpanForest
| Methods inherited from class java.lang.Object |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
MyPrimJarnik
public MyPrimJarnik()
genMinSpanForest
public void genMinSpanForest(AdjacencyMatrixGraph g)
- PrimJarnik's algorithm can be broken into several steps.
We first initialize a decoration that will track the distance
of each vertex in the graph from a Minimum spanning tree.
There are initially no MST's, so each vertex starts with a
distance of "Infinite" (for the purposes of this program,
you may use Integer.MAX_VALUE constant as infinite).
Next, we insert all the graph vertices into a priority queue,
using each of their distances as a key.
We then remove the vertex with the minimum distance from the
priority queue, and "relax" each of that vertex's incident
edges. To relax an edge, we examine the distance of the
adjacent vertex. If that weight is greater than the
connecting edge's weight, and the vertex is not already in
a minimum spanning tree, we change that vertex's distance
to be the weight of the connecting edge.
After all incident edges have been relaxed, we then add the
minimum key vertex to the MSF, along with the edge that most
recently "relaxed" that vertex (note: there may not be
such a vertex). You will want to decorate the vertex with edge
that most recently relaxed it. To do this use the DISCOVERY_EDGE
object. Please note that the DISCOVERY_EDGE should be applied
to the vertex, NOT the edge.
We continue this process until there are no vertices remaining
in the priority queue.
As with Kruskal's algorithm, you will not will *not* be returning a tree.
This is partly because there may be multiple MST's (hence a Minimum
Spanning Forest (MSF)). Instead, you will mark (by decorations) all
the edges that belong in an MST. You *must* use the MST_EDGE
decoration (which is predefined for you) to decorate edges in order
for the visualizer to correctly recognize an Edge as belonging to
an MST.
There are several other decorations that you may find useful:
DISTANCE
LOCATOR
TRUE
DISCOVERY_EDGE
- Specified by:
genMinSpanForest in interface MinSpanForest
- Parameters:
g - The graph to perform the algorithm on.- See Also:
SortedListAdaptablePriorityQueue,
CS16Edge,
This algorithm must run in O(n^2 log n) time where n is the number
of vertices. Note that this differs from the book because you are
using an adjacency matrix rather than an adjacency list.
cleanup
public void cleanup(AdjacencyMatrixGraph g)
- This will clean up any decorations that were added to the graph
as a result of running the genMinSpanForest(.)
algorithm. Specifically, this means removing all CLOUD
decorations from Vertex's and all MST_EDGE decorations from all
Edge's.
This must run in O(n + m) time. Where n is the number of vertices
and m is the number of edges.
- Specified by:
cleanup in interface MinSpanForest
- Parameters:
g - The graph to cleanup.