class EdgeComparator implements Comparator
public class MinimumSpanningTreeDemo
1: //MinimumSpanningTreeDemo.java
3: import java.util.ArrayList;
4: import java.util.Collection;
5: import java.util.Comparator;
6: import java.util.HashSet;
7: import java.util.List;
8: import java.util.PriorityQueue;
10: class EdgeComparator implements Comparator<Edge>
11: {
12: public int compare(Edge edge1, Edge edge2)
13: {
14: if (edge1.weight > edge2.weight)
15: {
16: return 1;
17: }
18: else if (edge1.weight < edge2.weight)
19: {
20: return -1;
21: }
22: return 0;
23: }
24: }
26: public class MinimumSpanningTreeDemo
27: {
28: // Returns a list of edges representing the graph's minimum spanning tree.
29: // Uses Kruskal's minimum spanning tree algorithm.
30: public static List<Edge> minimumSpanningTree(Graph graph)
31: {
32: // Get a collection of the graph's edges
33: Collection<Edge> allEdges = graph.getEdges();
35: // edgeQueue starts as a priority queue of all edges from the graph
36: PriorityQueue<Edge> edgeQueue;
37: edgeQueue = new PriorityQueue<Edge>
38: (
39: allEdges.size(),
40: new EdgeComparator()
41: );
42: edgeQueue.addAll(allEdges);
44: // Initialize the collection of vertex sets
45: VertexSetCollection vertexSets =
46: new VertexSetCollection(graph.getVertices());
48: // resultList is initially an empty list
49: ArrayList<Edge> resultList = new ArrayList<Edge>();
51: while (edgeQueue.size() > 0)
52: {
53: // Remove edge with minimum weight from edgeQueue
54: Edge nextEdge = edgeQueue.remove();
56: // set1 = set in vertexSets containing nextEdge's 'from' vertex
57: HashSet<Vertex> set1 = vertexSets.getSet(nextEdge.fromVertex);
58: // set2 = set in vertexSets containing nextEdge's 'to' vertex
59: HashSet<Vertex> set2 = vertexSets.getSet(nextEdge.toVertex);
61: // If the 2 sets are distinct, then merge
62: if (set1 != set2)
63: {
64: // Add nextEdge to resultList
65: resultList.add(nextEdge);
66: // Merge the 2 sets within the collection
67: vertexSets.merge(set1, set2);
68: }
69: }
71: return resultList;
72: }
74: public static void main(String[] args)
75: {
76: // Add vertices A through H to graph1
77: Graph graph1 = new Graph();
78: String[] vertexNames = { "A", "B", "C", "D", "E", "F", "G", "H" };
79: for (String vertexName : vertexNames)
80: {
81: graph1.addVertex(vertexName);
82: }
84: // Add graph1's edges
85: graph1.addUndirectedEdge(graph1.getVertex("A"),
86: graph1.getVertex("B"), 15);
87: graph1.addUndirectedEdge(graph1.getVertex("A"),
88: graph1.getVertex("D"), 6);
89: graph1.addUndirectedEdge(graph1.getVertex("B"),
90: graph1.getVertex("C"), 9);
91: graph1.addUndirectedEdge(graph1.getVertex("B"),
92: graph1.getVertex("D"), 12);
93: graph1.addUndirectedEdge(graph1.getVertex("B"),
94: graph1.getVertex("G"), 14);
95: graph1.addUndirectedEdge(graph1.getVertex("B"),
96: graph1.getVertex("H"), 10);
97: graph1.addUndirectedEdge(graph1.getVertex("C"),
98: graph1.getVertex("E"), 16);
99: graph1.addUndirectedEdge(graph1.getVertex("D"),
100: graph1.getVertex("E"), 8);
101: graph1.addUndirectedEdge(graph1.getVertex("E"),
102: graph1.getVertex("F"), 20);
104: // Add vertices A through G, and P, to graph2
105: Graph graph2 = new Graph();
106: String[] vertexNames2 = { "A", "B", "C", "D", "E", "F", "G", "P" };
107: for (String vertexName : vertexNames2)
108: {
109: graph2.addVertex(vertexName);
110: }
112: // Add graph2's edges
113: graph2.addUndirectedEdge(graph2.getVertex("A"),
114: graph2.getVertex("B"), 80);
115: graph2.addUndirectedEdge(graph2.getVertex("A"),
116: graph2.getVertex("C"), 105);
117: graph2.addUndirectedEdge(graph2.getVertex("A"),
118: graph2.getVertex("E"), 182);
119: graph2.addUndirectedEdge(graph2.getVertex("B"),
120: graph2.getVertex("C"), 90);
121: graph2.addUndirectedEdge(graph2.getVertex("B"),
122: graph2.getVertex("D"), 60);
123: graph2.addUndirectedEdge(graph2.getVertex("B"),
124: graph2.getVertex("P"), 100);
125: graph2.addUndirectedEdge(graph2.getVertex("C"),
126: graph2.getVertex("P"), 132);
127: graph2.addUndirectedEdge(graph2.getVertex("D"),
128: graph2.getVertex("E"), 80);
129: graph2.addUndirectedEdge(graph2.getVertex("E"),
130: graph2.getVertex("F"), 70);
131: graph2.addUndirectedEdge(graph2.getVertex("F"),
132: graph2.getVertex("G"), 72);
133: graph2.addUndirectedEdge(graph2.getVertex("F"),
134: graph2.getVertex("P"), 145);
135: graph2.addUndirectedEdge(graph2.getVertex("G"),
136: graph2.getVertex("P"), 180);
138: // Get the minimum spanning tree for both graphs
139: Graph[] graphs = { graph1, graph2 };
140: int graphNum = 1;
141: for (Graph graph : graphs)
142: {
143: // Get the list of edges for the graph's minimum spanning tree
144: List<Edge> treeEdges = minimumSpanningTree(graph);
146: // Display the list of edges
147: System.out.printf
148: (
149: "Edges in minimum spanning tree (graph %d):%n",
150: graphNum
151: );
152: for (Edge edge : treeEdges)
153: {
154: System.out.print
155: (
156: edge.fromVertex.label
157: + " to "
158: + edge.toVertex.label
159: );
160: System.out.printf
161: (
162: ", weight = %d%n",
163: (int)edge.weight
164: );
165: }
167: graphNum++;
168: }
169: }
170: }