logo
  • Home
  • About
  • Training
  • Programming
  • CS
  • IT
  • IS
  • ECE
  • EEE
  • EE
  • Civil
  • Mechanical
  • Chemical
  • Metallurgy
  • Instrumentation
  • Aeronautical
  • Aerospace
  • Biotechnology
  • Agriculture
  • MCA
  • BCA
  • Internship
  • Contact

Questions & Answers

C Interview Questions
C++ Questions
Linux MCQs
C# Quiz
Java MCQs
JavaScript MCQs
SAN Questions
PHP Questions
Python Quiz

Computer Science Questions

Operating System Quiz
Computer Architecture MCQs
Software Architecture MCQs
Software Engineering MCQs
Artificial Intelligence MCQs
LISP Programming MCQs
Database Management MCQs
Computer Network MCQs
Microprocessor MCQs

C Programming Examples

Simple C Programs
C - Arrays
C - Matrix
C - Strings
C - Bitwise Operations
C - Linked Lists
C - Stacks & Queues
C - Searching & Sorting
C - Trees
C - Strings
C - File Handling
C - Mathematical Functions
C - Puzzles & Games
C Programs - Recursion
C Programs - No Recursion

Java Algorithms

Java - Numerical Problems
Java - Combinatorial Problems
Java - Graph Problems
Java - Hard Graph Problems
Java - Computation Geometry
Java - Sets & Strings
Java - Data-Structures
Java - Collection API Problems

C++ Algorithms

C++ - Numerical Problems
C++ - Combinatorial Problems
C++ - Graph Problems
C++ - Hard Graph Problems
C++ - Computation Geometry
C++ - Sets & Strings
C++ - Data-Structures
C++ - STL Library

C Algorithms

C - Numerical Problems
C - Combinatorial Problems
C - Graph Problems
C - Hard Graph Problems
C - Computation Geometry
C - Sets & Strings
C - Data-Structures

« Prev Page
Next Page »

Java Program to Use Boruvka’s Algorithm to Find the Minimum Spanning Tree

Posted on October 21, 2014 by dharmendra
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.                     {
  44.                         mst.add(e);
  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.  
  184.     public void add(Item item)
  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;
  234.     private Bag<Edge>[] adj;
  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.         {
  250.             adj[v] = new Bag<Edge>();
  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);
  268.             addEdge(e);
  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.  
  283.     public void addEdge(Edge e)
  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));
  293.         adj[v].add(e);
  294.         adj[w].add(e);
  295.     }
  296.  
  297.     public Iterable<Edge> adj(int v)
  298.     {
  299.         if (v < 0 || v >= V)
  300.             throw new IndexOutOfBoundsException("vertex " + v
  301.                     + " is not between 0 and " + (V - 1));
  302.         return adj[v];
  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.                 {
  315.                     list.add(e);
  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)
  322.                         list.add(e);
  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.

Here’s the list of Best Reference Books in Java Programming, Data Structures and Algorithms.

« Prev Page - Java Program to Use the Bellman-Ford Algorithm to Find the Shortest Path Between Two Vertices Assuming that Negative Size Edges Exist in the Graph
» Next Page - Java Program to Create a Random Linear Extension for a DAG
« Java Program to Use the Bellman-Ford Algorithm to Find the Shortest Path Between Two Vertices Assuming that Negative Size Edges Exist in the Graph
Java Program to Create a Random Linear Extension for a DAG »

Deep Dive @ Sanfoundry:

  1. Java Programming Examples on Computational Geometry Problems & Algorithms
  2. Java Programming Examples on Data-Structures
  3. C++ Programming Examples on Graph Problems & Algorithms
  4. C++ Programming Examples on Hard Graph Problems & Algorithms
  5. Java Programming Examples on Combinatorial Problems & Algorithms
  6. C Programming Examples on Hard Graph Problems & Algorithms
  7. C Programming Examples on Graph Problems & Algorithms
  8. Java Programming Examples on Graph Problems & Algorithms
  9. Java Programming Examples on Hard Graph Problems & Algorithms
  10. STP – Spanning Tree Protocol Training
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer and SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage & Cluster Administration, Advanced C Programming, SAN Storage Technologies, SCSI Internals and Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him below:
LinkedIn | Facebook | Twitter | Google+

Best Careers

Developer Tracks
SAN Developer
Linux Kernel Developer
Linux Driver Developer
Linux Network Developer

Live Training Photos
Mentoring
Software Productivity
GDB Assignment
Sanfoundry is No. 1 choice for Deep Hands-ON Trainings in SAN, Linux & C, Kernel Programming. Our Founder has trained employees of almost all Top Companies in India such as VMware, Citrix, Oracle, Motorola, Ericsson, Aricent, HP, Intuit, Microsoft, Cisco, SAP Labs, Siemens, Symantec, Redhat, Chelsio, Cavium, ST-Micro, Samsung, LG-Soft, Wipro, TCS, HCL, IBM, Accenture, HSBC, Mphasis, Tata-Elxsi, Tata VSNL, Mindtree, Cognizant and Startups.

Best Trainings

SAN I - Technology
SAN II - Admin
Linux Fundamentals
Advanced C Training
Linux-C Debugging
System Programming
Network Programming
Linux Threads
Kernel Programming
Kernel Debugging
Linux Device Drivers

Best Reference Books

Computer Science Books
Algorithm & Programming Books
Electronics Engineering Books
Electrical Engineering Books
Chemical Engineering Books
Civil Engineering Books
Mechanical Engineering Books
Industrial Engineering Books
Instrumentation Engg Books
Metallurgical Engineering Books
All Stream Best Books

Questions and Answers

1000 C Questions & Answers
1000 C++ Questions & Answers
1000 C# Questions & Answers
1000 Java Questions & Answers
1000 Linux Questions & Answers
1000 Python Questions
1000 PHP Questions & Answers
1000 Hadoop Questions
Cloud Computing Questions
Computer Science Questions
All Stream Questions & Answers

India Internships

Computer Science Internships
Instrumentation Internships
Electronics Internships
Electrical Internships
Mechanical Internships
Industrial Internships
Systems Internships
Chemical Internships
Civil Internships
IT Internships
All Stream Internships

About Sanfoundry

About Us
Copyright
TOS & Privacy
Jobs
Bangalore Training
Online Training
SAN Training
Developers Track
Mentoring Sessions
Contact Us
Sitemap
© 2011 Sanfoundry