Minimum Spanning Tree

Aim: - Construction of Minimum Spanning Tree for a given connected graph

A spanning tree of any graph is a sub-graph that should be connected, acyclic, and consisting of |V|-1 edges. A single graph can have many different spanning trees. A minimum spanning tree (MST) is a spanning tree with weight less than or equal to the weight of every other spanning tree.

Example:-

There are two popular algorithms to find MST for a given weighted graph

Prim's Algorithm

Prim's algorithm slowly grows a minimum spanning tree, starting from a single vertex and adding new vertex which is nearest. This algorithm works based on the vertices of a given graph.

1.      Pick any vertex as a starting vertex (Call it v) and mark it as visited.

2.      Find the nearest neighbor of v (call it u). Mark it as visited and keep this edge (v-u) in MST

3.      Find the nearest unvisited neighbor of any visited vertex, Mark it and keep this edge also in MST

4.      Repeat Step 3 until all vertices are marked visited        

Kruskal's Algorithm

The algorithm begins by sorting the graph’s edges in ascending order of their weights. This algorithm works based on the edges of a given graph.

1.      Sort the weights of all the edges in ascending order

2.      Find the minimum weight edge in the graph and mark it for MST

3.      Find the next smallest unmarked edge in the graph that doesn't create circuit. Mark this edge also in MST

4.      Repeat Step 3 until you reach out to |V|-1 edges 

 

Program to find minimum Spanning tree for a given graph using Prim’s Algorithm

import java.io.*;

import java.util.*;

class SpanTree {

    LinkedList<Integer> cost ;

    LinkedList<Integer> ver;

    LinkedList<Integer> Ev1;

    LinkedList<Integer> Ev2;

    int n;

    SpanTree(int a)throws Exception  {

        n=a;

        cost=new LinkedList<Integer>();

        ver=new LinkedList<Integer>();

        Ev1=new LinkedList<Integer>();

        Ev2=new LinkedList<Integer>();

    }

    public void Read_cost()throws IOException  {

        DataInputStream in=new DataInputStream(System.in);

        System.out.println(" Enter cost matrix of "+n+" vertices ");

        for(int i=0;i<n;i++)

            for(int j=0;j<n;j++)

                cost.addLast(Integer.parseInt(in.readLine()));

    }

    public int find_MST()  {

         boolean visited[]=new boolean[10];

         int i,j,k=0,s,u=-1,v,min,tot_cost=0;

         for(i=0;i<n;i++)

           visited[i]=false;

         visited[0]=true;

         ver.addFirst(0);

         v=0;

         do{

             k++;

             min=999;

             for(s=0;s<k;s++) {

                 i=ver.get(s);

                 for(j=0;j<n;j++)  {

                     if(i==j)

                         continue;

                     if(!visited[j] && cost.get(i*n+j)<min) {

                         min=cost.get(i*n+j);

                         v=i;    u=j;

                     }

                }

             }

             tot_cost+=min;

             ver.addLast(u);

             visited[u]=true;

             Ev1.addLast(v);

             Ev2.addLast(u);

          }while(k<n-1);

          return tot_cost;

    }

    public void DispMST() {

       System.out.println(" The edges in the Minimum Spanning Tree are ");

       for(int i=0;i<n-1;i++)

         System.out.println((Ev1.get(i) +1)+"----"+(Ev2.get(i) +1));

    }

}

public class MST {

    public static void main(String args[]) throws Exception  {

        DataInputStream in=new DataInputStream(System.in);

        int n;

        System.out.print(" Enter how many  vertices ");

        n=Integer.parseInt(in.readLine());

        SpanTree t=new SpanTree(n);

        t.Read_cost();

        System.out.println(" Total cost of MST is ===> "+t.find_MST());

        t.DispMST();

     }

}

 

 

OUTPUT:

Enter how many vertices 5

Enter cost matrix of 5 vertices

0   5    4   99  1

4   0   99   4   1

4   99  0   6   2

99  4   6   0   3

 1    1    2   3   0

 

Total cost of MST is ===> 7

The edges in the Minimum Spanning Tree are

1----5

5----2

5----3

5----4