Interface SpanningTreeAlgorithm is implemented by
algorithms that compute the minimum spanning tree of a graph.
Two types of data structures are supported by the interface:
(1) an adjacency-matrix and (2) an adjacency-list.
Algorithm| Method Summary | |
double |
getTreeWeight()
Method getTreeWeight should return the weight
of the minimum spanning tree that was computed most recently. |
void |
initialize(int numVertices)
Method initialize will be given the number
of vertices. |
double[][] |
minimumSpanningTree(double[][] adjMatrix)
Method minimumSpanningTree will be given an
adjacency matrix of an undirected graph and will be
expected to return the adjacency matrix corresponding to
the minimum spanning tree. |
GraphVertex[] |
minimumSpanningTree(GraphVertex[] adjList)
Method minimumSpanningTree will be given an
adjacency list of an undirected graph and will be expected
to return the adjacency-list corresponding to the minimum
spanning tree. |
| Methods inherited from interface edu.gwu.algtest.Algorithm |
getName, setPropertyExtractor |
| Method Detail |
public void initialize(int numVertices)
initialize will be given the number
of vertices.numVertices - an int valuepublic double[][] minimumSpanningTree(double[][] adjMatrix)
minimumSpanningTree will be given an
adjacency matrix of an undirected graph and will be
expected to return the adjacency matrix corresponding to
the minimum spanning tree. Note that each matrix
entry is a positive edge weight; if there is no edge, the
weight will be zero.adjMatrix - a double[][] valuedouble[][] valuepublic GraphVertex[] minimumSpanningTree(GraphVertex[] adjList)
minimumSpanningTree will be given an
adjacency list of an undirected graph and will be expected
to return the adjacency-list corresponding to the minimum
spanning tree. Each GraphVertex instance
contains a linked list of edges that are incident to that
vertex. Since the adjacency list is the array of such
"edge lists", the input is an array of GraphVertex
instances. Note that the list for each vertex consists of edges
represented by instances of the class GraphEdge.adjList - a GraphVertex[] valueGraphVertex[] valuepublic double getTreeWeight()
getTreeWeight should return the weight
of the minimum spanning tree that was computed most recently.
The idea is, one of the two minimumSpanningTree
methods will first be called and should compute the tree,
including its weight. Then, this method will be called simply
to retrieve the weight.double value