# Java Program to Find Minimum Spanning Tree using Boruvka’s Algorithm

This is a java program to find the minimum spanning tree of a graph. Given a connected, undirected graph, a spanning tree of that graph is a subgraph that is a tree and connects all the vertices together. A single graph can have many different spanning trees. We can also assign a weight to each edge, which is a number representing how unfavorable it is, and use this to assign a weight to a spanning tree by computing the sum of the weights of the edges in that spanning tree. A minimum spanning tree (MST) or minimum weight spanning tree is then a spanning tree with weight less than or equal to the weight of every other spanning tree. More generally, any undirected graph (not necessarily connected) has a minimum spanning forest, which is a union of minimum spanning trees for its connected components.

Here is the source code of the Java Program to Use Boruvka’s Algorithm to Find the Minimum Spanning Tree. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

1.
2. package com.sanfoundry.graph;
3.
4. import java.util.Iterator;
5. import java.util.NoSuchElementException;
6. import java.util.Scanner;
7.
8. public class BoruvkasMST
9. {
10.     private Bag<Edge> mst = new Bag<Edge>();    // Edge in MST
11.     private double weight;                      // weight of MST
12.
13.     public BoruvkasMST(EdgeWeightedGraph G)
14.     {
15.         UF uf = new UF(G.V());
16.         // repeat at most log V times or until we have V-1 Edge
17.         for (int t = 1; t < G.V() && mst.size() < G.V() - 1; t = t + t)
18.         {
19.             // foreach tree in forest, find closest edge
20.             // if edge weights are equal, ties are broken in favor of first edge
21.             // in G.Edge()
22.             Edge[] closest = new Edge[G.V()];
23.             for (Edge e : G.Edge())
24.             {
25.                 int v = e.either(), w = e.other(v);
26.                 int i = uf.find(v), j = uf.find(w);
27.                 if (i == j)
28.                     continue;   // same tree
29.                 if (closest[i] == null || less(e, closest[i]))
30.                     closest[i] = e;
31.                 if (closest[j] == null || less(e, closest[j]))
32.                     closest[j] = e;
33.             }
34.             // add newly discovered Edge to MST
35.             for (int i = 0; i < G.V(); i++)
36.             {
37.                 Edge e = closest[i];
38.                 if (e != null)
39.                 {
40.                     int v = e.either(), w = e.other(v);
41.                     // don't add the same edge twice
42.                     if (!uf.connected(v, w))
43.                     {
45.                         weight += e.weight();
46.                         uf.union(v, w);
47.                     }
48.                 }
49.             }
50.         }
51.         // check optimality conditions
52.         assert check(G);
53.     }
54.
55.     public Iterable<Edge> Edge()
56.     {
57.         return mst;
58.     }
59.
60.     public double weight()
61.     {
62.         return weight;
63.     }
64.
65.     // is the weight of edge e strictly less than that of edge f?
66.     private static boolean less(Edge e, Edge f)
67.     {
68.         return e.weight() < f.weight();
69.     }
70.
71.     // check optimality conditions (takes time proportional to E V lg* V)
72.     private boolean check(EdgeWeightedGraph G)
73.     {
74.         // check weight
75.         double totalWeight = 0.0;
76.         for (Edge e : Edge())
77.         {
78.             totalWeight += e.weight();
79.         }
80.         double EPSILON = 1E-12;
81.         if (Math.abs(totalWeight - weight()) > EPSILON)
82.         {
83.             System.err.printf(
84.                     "Weight of Edge does not equal weight(): %f vs. %f\n",
85.                     totalWeight, weight());
86.             return false;
87.         }
88.         // check that it is acyclic
89.         UF uf = new UF(G.V());
90.         for (Edge e : Edge())
91.         {
92.             int v = e.either(), w = e.other(v);
93.             if (uf.connected(v, w))
94.             {
95.                 System.err.println("Not a forest");
96.                 return false;
97.             }
98.             uf.union(v, w);
99.         }
100.         // check that it is a spanning forest
101.         for (Edge e : G.Edge())
102.         {
103.             int v = e.either(), w = e.other(v);
104.             if (!uf.connected(v, w))
105.             {
106.                 System.err.println("Not a spanning forest");
107.                 return false;
108.             }
109.         }
110.         // check that it is a minimal spanning forest (cut optimality
111.         // conditions)
112.         for (Edge e : Edge())
113.         {
114.             // all Edge in MST except e
115.             uf = new UF(G.V());
116.             for (Edge f : mst)
117.             {
118.                 int x = f.either(), y = f.other(x);
119.                 if (f != e)
120.                     uf.union(x, y);
121.             }
122.             // check that e is min weight edge in crossing cut
123.             for (Edge f : G.Edge())
124.             {
125.                 int x = f.either(), y = f.other(x);
126.                 if (!uf.connected(x, y))
127.                 {
128.                     if (f.weight() < e.weight())
129.                     {
130.                         System.err.println("Edge " + f
131.                                 + " violates cut optimality conditions");
132.                         return false;
133.                     }
134.                 }
135.             }
136.         }
137.         return true;
138.     }
139.
140.     public static void main(String[] args)
141.     {
142.         Scanner sc = new Scanner(System.in);
143.         System.out.println("Enter the number of verties: ");
144.         EdgeWeightedGraph G = new EdgeWeightedGraph(sc.nextInt());
145.         BoruvkasMST mst = new BoruvkasMST(G);
146.         System.out.println("MST: ");
147.         for (Edge e : mst.Edge())
148.         {
149.             System.out.println(e);
150.         }
151.         System.out.printf("Total weight of MST: %.5f\n", mst.weight());
152.         sc.close();
153.     }
154. }
155.
156. class BagOfItems<Item> implements Iterable<Item>
157. {
158.     private int N;               // number of elements in bag
159.     private Node<Item> first;    // beginning of bag
160.
161.     // helper linked list class
162.     private static class Node<Item>
163.     {
164.         private Item item;
165.         private Node<Item> next;
166.     }
167.
168.     public BagOfItems()
169.     {
170.         first = null;
171.         N = 0;
172.     }
173.
174.     public boolean isEmpty()
175.     {
176.         return first == null;
177.     }
178.
179.     public int size()
180.     {
181.         return N;
182.     }
183.
185.     {
186.         Node<Item> oldfirst = first;
187.         first = new Node<Item>();
188.         first.item = item;
189.         first.next = oldfirst;
190.         N++;
191.     }
192.
193.     public Iterator<Item> iterator()
194.     {
195.         return new ListIterator<Item>(first);
196.     }
197.
198.     // an iterator, doesn't implement remove() since it's optional
199.     @SuppressWarnings("hiding")
200.     private class ListIterator<Item> implements Iterator<Item>
201.     {
202.         private Node<Item> current;
203.
204.         public ListIterator(Node<Item> first)
205.         {
206.             current = first;
207.         }
208.
209.         public boolean hasNext()
210.         {
211.             return current != null;
212.         }
213.
214.         public void remove()
215.         {
216.             throw new UnsupportedOperationException();
217.         }
218.
219.         public Item next()
220.         {
221.             if (!hasNext())
222.                 throw new NoSuchElementException();
223.             Item item = current.item;
224.             current = current.next;
225.             return item;
226.         }
227.     }
228. }
229.
230. class EdgeWeightedGraph
231. {
232.     private final int V;
233.     private final int E;
235.
236.     @SuppressWarnings("unchecked")
237.     public EdgeWeightedGraph(int V)
238.     {
239.         Scanner sc = new Scanner(System.in);
240.         if (V < 0)
241.         {
242.             sc.close();
243.             throw new IllegalArgumentException(
244.                     "Number of vertices must be nonnegative");
245.         }
246.         this.V = V;
247.         adj = (Bag<Edge>[]) new Bag[V];
248.         for (int v = 0; v < V; v++)
249.         {
251.         }
252.         System.out.println("Enter the number of Edge: ");
253.         E = sc.nextInt();
254.         if (E < 0)
255.         {
256.             sc.close();
257.             throw new IllegalArgumentException(
258.                     "Number of Edge must be nonnegative");
259.         }
260.         System.out.println("Enter the Edge: <from> <to>");
261.         for (int i = 0; i < E; i++)
262.         {
263.             int v = sc.nextInt();
264.             int w = sc.nextInt();
265.             double weight = Math.round(100 * Math.random()) / 100.0;
266.             System.out.println(weight);
267.             Edge e = new Edge(v, w, weight);
269.         }
270.         sc.close();
271.     }
272.
273.     public int V()
274.     {
275.         return V;
276.     }
277.
278.     public int E()
279.     {
280.         return E;
281.     }
282.
284.     {
285.         int v = e.either();
286.         int w = e.other(v);
287.         if (v < 0 || v >= V)
288.             throw new IndexOutOfBoundsException("vertex " + v
289.                     + " is not between 0 and " + (V - 1));
290.         if (w < 0 || w >= V)
291.             throw new IndexOutOfBoundsException("vertex " + w
292.                     + " is not between 0 and " + (V - 1));
295.     }
296.
298.     {
299.         if (v < 0 || v >= V)
300.             throw new IndexOutOfBoundsException("vertex " + v
301.                     + " is not between 0 and " + (V - 1));
303.     }
304.
305.     public Iterable<Edge> Edge()
306.     {
307.         Bag<Edge> list = new Bag<Edge>();
308.         for (int v = 0; v < V; v++)
309.         {
310.             int selfLoops = 0;
311.             for (Edge e : adj(v))
312.             {
313.                 if (e.other(v) > v)
314.                 {
316.                 }
317.                 // only add one copy of each self loop (self loops will be
318.                 // consecutive)
319.                 else if (e.other(v) == v)
320.                 {
321.                     if (selfLoops % 2 == 0)
323.                     selfLoops++;
324.                 }
325.             }
326.         }
327.         return list;
328.     }
329.
330.     public String toString()
331.     {
332.         String NEWLINE = System.getProperty("line.separator");
333.         StringBuilder s = new StringBuilder();
334.         s.append(V + " " + E + NEWLINE);
335.         for (int v = 0; v < V; v++)
336.         {
337.             s.append(v + ": ");
338.             for (Edge e : adj[v])
339.             {
340.                 s.append(e + "  ");
341.             }
342.             s.append(NEWLINE);
343.         }
344.         return s.toString();
345.     }
346. }
347.
348. class Edge implements Comparable<Edge>
349. {
350.     private final int v;
351.     private final int w;
352.     private final double weight;
353.
354.     public Edge(int v, int w, double weight)
355.     {
356.         if (v < 0)
357.             throw new IndexOutOfBoundsException(
358.                     "Vertex name must be a nonnegative integer");
359.         if (w < 0)
360.             throw new IndexOutOfBoundsException(
361.                     "Vertex name must be a nonnegative integer");
362.         if (Double.isNaN(weight))
363.             throw new IllegalArgumentException("Weight is NaN");
364.         this.v = v;
365.         this.w = w;
366.         this.weight = weight;
367.     }
368.
369.     public double weight()
370.     {
371.         return weight;
372.     }
373.
374.     public int either()
375.     {
376.         return v;
377.     }
378.
379.     public int other(int vertex)
380.     {
381.         if (vertex == v)
382.             return w;
383.         else if (vertex == w)
384.             return v;
385.         else
386.             throw new IllegalArgumentException("Illegal endpoint");
387.     }
388.
389.     public int compareTo(Edge that)
390.     {
391.         if (this.weight() < that.weight())
392.             return -1;
393.         else if (this.weight() > that.weight())
394.             return +1;
395.         else
396.             return 0;
397.     }
398.
399.     public String toString()
400.     {
401.         return String.format("%d-%d %.5f", v, w, weight);
402.     }
403. }
404.
405. class UF
406. {
407.     private int[] id;     // id[i] = parent of i
408.     private byte[] rank;  // rank[i] = rank of subtree rooted at i (cannot be
409.                          // more than 31)
410.     private int count;    // number of components
411.
412.     public UF(int N)
413.     {
414.         if (N < 0)
415.             throw new IllegalArgumentException();
416.         count = N;
417.         id = new int[N];
418.         rank = new byte[N];
419.         for (int i = 0; i < N; i++)
420.         {
421.             id[i] = i;
422.             rank[i] = 0;
423.         }
424.     }
425.
426.     public int find(int p)
427.     {
428.         if (p < 0 || p >= id.length)
429.             throw new IndexOutOfBoundsException();
430.         while (p != id[p])
431.         {
432.             id[p] = id[id[p]];    // path compression by halving
433.             p = id[p];
434.         }
435.         return p;
436.     }
437.
438.     public int count()
439.     {
440.         return count;
441.     }
442.
443.     public boolean connected(int p, int q)
444.     {
445.         return find(p) == find(q);
446.     }
447.
448.     public void union(int p, int q)
449.     {
450.         int i = find(p);
451.         int j = find(q);
452.         if (i == j)
453.             return;
454.         // make root of smaller rank point to root of larger rank
455.         if (rank[i] < rank[j])
456.             id[i] = j;
457.         else if (rank[i] > rank[j])
458.             id[j] = i;
459.         else
460.         {
461.             id[j] = i;
462.             rank[i]++;
463.         }
464.         count--;
465.     }
466. }

Output:

\$ javac BoruvkasMST.java
\$ java BoruvkasMST

Enter the number of verties:
6
Enter the number of Edge:
7
Enter the Edge: <from> <to>
0 1
0.09
1 2
0.48
1 3
0.52
3 4
0.43
4 5
0.98
5 3
0.07
5 2
0.1
MST:
1-2 0.48000
3-4 0.43000
5-3 0.07000
5-2 0.10000
0-1 0.09000
Total weight of MST: 1.17000

Sanfoundry Global Education & Learning Series – 1000 Java Programs.