support.graph
Interface MinSpanForest

All Known Implementing Classes:

MyKruskal, MyPrimJarnik

public interface MinSpanForest

This class is a takeoff of Kruskal's minimum spanning tree algorithm. It has been extended to calculate the MST of each disconnected graph at the same time. The trick is to take advantage of the fact that Kruskal's algorithm combines "clouds" when it builds its trees. Thus we can connect the clouds of these disconnect graphs using the standard algorithm. The only modification to the original algorithm is specifying the termination case. Since the graphs can be disconnected, we can not stop the algorithm once we have n-1 edges in our MST. See the comments for genMinSpanForest(.) for an explanation of Kruskal's algorithm. This also makes heavy use of the decorable pattern, so make sure you know it cold.

Method Summary

CS16Edge[]

genMinSpanForest(AdjacencyMatrixGraph g, CS16GraphVisualizer visualizer) This method implements Kruskal's algorithm and extends it slightly to account for disconnected graphs.

Method Detail

genMinSpanForest

CS16Edge[] genMinSpanForest(AdjacencyMatrixGraph g,
                            CS16GraphVisualizer visualizer)

This method implements Kruskal's algorithm and extends it slightly to account for disconnected graphs. Kruskal's algorithm has three phases. In the first phase, we have to put each Vertex of the graph in its own 'cluster'. In Java, we represent a cluster by a NodeSequence. Thus, there will be n NodeSequences initially, where n is the number of nodes in the graph. In the second phase, we insert all the edges into a priority queue using the weight of each edge as its key. In terms of this algorithm, you may assume that the 'element' of the edge is an Integer storing the weight. Thus, to get the weight of an edge, all I would have to do is: int weight = ((Integer)theEdge.element()).intValue(); Now, we have a choice of priority queues that we could use. However, in order to get the best running times, the best one to use is ArrayHeap. In the third stage, we keep obtaining the edge with minimum weight. If the connecting Vertex's of the edge belong to different clouds, we merge the clouds. In order to get this method to run in the correct running time, each Vertex has to know which cloud it is in. Again, we can use the decorable pattern to accomplish this. Specifically, you can use the predefined CLOUD object as your decoration key. *This is important!* You will *not* be returning a tree. This is partly because there may be multiple MST's (hence a 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 that an Edge as belonging to an MST.

Parameters:

g - The graph to perform the algorithm on.

visualizer - The graph visualizer. Used to animate the MST algorithm.

See Also:

jdsl.core.ref.NodeSequence, jdsl.core.ref.ArrayHeap, This algorithm must run in O(n log n) time.