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

Tree traversal

Aim: - To learn about different Tree Traversal techniques

Tree traversal or traversing a tree examines all the nodes of the tree. There are two aspects to traversing a tree. One is that we need to follow references (pointers) from parent to child. The second is that we need to “visit” the node for some computation, e.g. getting or setting a field of an element referenced by that node. There are several different ways in which we can traverse a tree. They differ in the order in which the nodes are visited

Depth-first Traversals

In these traversals, a node and all its descendents are visited before the next sibling is visited. There are three ways to do depth-first-traversal of a tree, depending on whether you visit a node before its descendents or after its descendents.

There are three Depth-first Traversals

Preorder :- Performs the following operations recursively at each node

1.      Visit the root.

2.      Traverse the left subtree.

3.      Traverse the right subtree.

Inorder :- Performs the following operations recursively at each node

1.      Traverse the left subtree.

2.      Visit the root.

3.      Traverse the right subtree

Postorder :- Performs the following operations recursively at each node

1.      Traverse the left subtree.

2.      Traverse the right subtree.

3.      Visit the root.

Breadth-first Traversal

Trees can also be traversed in level-order, where we visit every node on a level before going to a lower level.

Java Program to implement Tree traversal

 

import java.io.*;

class BinTree{

    private Node root;

    private static class Node{

        Node left;

        Node right;

        int data;

        public Node(int cdata){

            left=null;

            right=null;

            data=cdata;

        }

    }

 

    public BinTree() throws Exception {

            root=null;

    }

 

    public void insert(int data)  {

        root=insert(root,data);

    }

 

    public Node insert(Node node,int data)  {

        if(node==null)

            node=new Node(data);

        else if(data<=node.data)

            node.left=insert(node.left, data);

        else

            node.right=insert(node.right, data);

        return(node);

    }

    public void Disp(int ch)  {

        if(root==null)

           System.out.println(" No Elements in the Tree ") ;

        else

         {

            switch(ch)

            {

                case 1: System.out.println("\n\n\n Preorder Traversal  ");

                        preorder(root);

                        break;

                case 2: System.out.println("\n\n\n Inorder Traversal  ");

                        inorder(root);

                        break;

                case 3: System.out.println("\n\n\n Postorder Traversal  ");

                        postorder(root);

                        break;

                case 4: System.out.println(" Height of the tree = "+height(root));

                        break;

                case 0: break;

                default:

                        System.out.println(" Invalid choice ") ;

             }

          }

     }

    

public int height(Node node) {

            if(node==null)

                return(0);

             return max( height(node.left)+1, height(node.right)+1);

      }

      int max(int a,int b) {

            return(a>b?a:b);               

      }

      public void preorder(Node node) {

        if(node!=null)

       {

            System.out.print("  "+node.data);

            preorder(node.left);

            preorder(node.right);

         }

      }

      public void inorder(Node node) {

        if(node!=null)

       {

            inorder(node.left);

            System.out.print("  "+node.data);

            inorder(node.right);

        }

     }

     public void postorder(Node node)  {

        if(node!=null)

       {

            postorder(node.left);

            postorder(node.right);

            System.out.print("   "+node.data);

        }

     }

}

 

public class Traversal {

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

        BinTree B= new BinTree();

        int n, item;

        DataInputStream in= new DataInputStream(System.in);

        System.out.print("Enter number of items to be inserted ");

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

        System.out.println("Enter any "+n+" integers ");

        while(n>0)  

        {

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

            B.insert(item);      

            n--;

        }

        int choice;

        do

        {

          System.out.println("\n Binary Tree Traversal operation ");

          System.out.println(" Enter the choice \n\t\t 1.preorder\n\t\t 2.inoreder\n\t\t 3.postorder\n\t\t  4.height of tree \n\t\t 0.Exit\n");

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

          B.Disp(choice);

        }while(choice!=0);

     }

}

OUTPUT:

Enter number of items to be inserted 8

Enter any 8 integers

4  3  5  6  7  2  1  8

 Binary Tree Traversal operation

 Enter the choice

                 1.preorder

                 2.inoreder

                 3.postorder

                 4.height of tree

                 0.Exit

1

 Preorder Traversal    4  3  2  1  5  6  7  8

 Binary Tree Traversal operation

 Enter the choice

                 1.preorder

                 2.inoreder

                 3.postorder

                 4.height of tree

                 0.Exit

2

 Inorder Traversal    1  2  3  4  5  6  7  8

 Binary Tree Traversal operation

 Enter the choice

                 1.preorder

                 2.inoreder

                 3.postorder

                 4.height of tree

                 0.Exit

3

 Postorder Traversal     1   2   3   8   7   6   5   4

Binary Tree Traversal operation

 Enter the choice

                 1.preorder

                 2.inoreder

                 3.postorder

                 4.height of tree

                 0.Exit

4

 Height of the tree = 5

 Binary Tree Traversal operation

 Enter the choice

                 1.preorder

                 2.inoreder

                 3.postorder

                 4.height of tree

                 0.Exit

0