Thursday, April 14, 2011

Kruskal’s algorithm


import java.io.*;
  import java.util.*;
  class Graph
  {
  int i,n; //no of nodes
  int noe; //no edges in the graph
  int graph_edge[][]=new int[100][4];d
  int tree[][]=new int [10][10];
  int sets[][]=new int[100][10];
  int top[]=new int[100];
  int cost=0;
  void read_graph()
  {
                System.out.print("Enter the no. of nodes in the undirected weighted graph ::");
                n=getNumber();
                noe=0;
                System.out.println("Enter the weights for the following edges ::\n");
                for(int i=1;i<=n;i++)
                {
                                for(int j=i+1;j<=n;j++)
                                {
                                                System.out.print(" < "+i+" , "+j+" > ::");
                                                int w;
                                                w=getNumber();
                                                if(w!=0)
                                                {
                                                                noe++;
                                                                graph_edge[noe][1]=i;
                                                                graph_edge[noe][2]=j;
                                                                graph_edge[noe][3]=w;
                                                }
                                }
                }
  }

  void sort_edges()
  {
  /**** Sort the edges using bubble sort in increasing order**************/
                for(int i=1;i<=noe-1;i++)
                {
                                for(int j=1;j<=noe-i;j++)
                                {
                                                if(graph_edge[j][3]>graph_edge[j+1][3])
                                                {
                                                                int t=graph_edge[j][1];
                                                                graph_edge[j][1]=graph_edge[j+1][1];
                                                                graph_edge[j+1][1]=t;
                                                                t=graph_edge[j][2];
                                                                graph_edge[j][2]=graph_edge[j+1][2];
                                                                graph_edge[j+1][2]=t;

                                                                t=graph_edge[j][3];
                                                                graph_edge[j][3]=graph_edge[j+1][3];
                                                                graph_edge[j+1][3]=t;
                                                }
                                }
                }
  }

  void algorithm()
  {
                // ->make a set for each node
                for(int i=1;i<=n;i++)
                {
                                sets[i][1]=i;
                                top[i]=1;
                }

                System.out.println("\nThe algorithm starts ::\n\n");

                for(i=1;i<=noe;i++)
                {
                                int p1=find_node(graph_edge[i][1]);
                                int p2=find_node(graph_edge[i][2]);

                                if(p1!=p2)
                                {
                                                System.out.print("The edge included in the tree is ::");
                                                System.out.print("< "+graph_edge[i][1]+" , ");
                                                System.out.println(graph_edge[i][2]+" > ");;
                                                cost=cost+graph_edge[i][3];

                                                  tree[graph_edge[i][1]][graph_edge[i][2]]=graph_edge[i][3];
                                                  tree[graph_edge[i][2]][graph_edge[i][1]]=graph_edge[i][3];

                                                // Mix the two sets

                                                for(int j=1;j<=top[p2];j++)
                                                {
                                                top[p1]++;
                                                sets[p1][top[p1]]=sets[p2][j];
                                                }
                                                top[p2]=0;
                                }
                                else
                                {
                                                System.out.println("Inclusion of the edge ");
                                                System.out.print(" < "+graph_edge[i][1]+" , ");
                                                System.out.println(graph_edge[i][2]+"> forms a cycle so   it is removed\n\n");
                                }
                }

                System.out.println("Cost of the spanning tree : "+cost);
  }

  int find_node(int n)
  {
                for(int i=1;i<=noe;i++)
                {
                                for(int j=1;j<=top[i];j++)
                                {
                                                if(n==sets[i][j])
                                                return i;
                                }
                }
                return -1;
                }
  }

  class Kruskal1
  {
  public static void main(String args[])
  {
                Graph obj=new Graph();
                obj.read_graph();
                obj.sort_edges();
                obj.algorithm();
  }
  }

/*
  Enter the no. of nodes in the undirected weighted graph ::6
  Enter the weights for the following edges ::

  < 1 , 2 > ::3
  < 1 , 3 > ::1
  < 1 , 4 > ::6
  < 1 , 5 > ::0
  < 1 , 6 > ::0
  < 2 , 3 > ::5
  < 2 , 4 > ::0
  < 2 , 5 > ::3
  < 2 , 6 > ::0
  < 3 , 4 > ::5
  < 3 , 5 > ::6
  < 3 , 6 > ::4
  < 4 , 5 > ::0
  < 4 , 6 > ::2
  < 5 , 6 > ::6

  The algorithm starts ::


  The edge included in the tree is ::< 1 , 3 >
  The edge included in the tree is ::< 4 , 6 >
  The edge included in the tree is ::< 1 , 2 >
  The edge included in the tree is ::< 2 , 5 >
  The edge included in the tree is ::< 3 , 6 >
  Inclusion of the edge
   < 2 , 3> forms a cycle so it is removed


   Inclusion of the edge
    < 3 , 4> forms a cycle so it is removed


  Inclusion of the edge
   < 1 , 4> forms a cycle so it is removed


  Inclusion of the edge
   < 3 , 5> forms a cycle so it is removed


  Inclusion of the edge
   < 5 , 6> forms a cycle so it is removed


   Cost of the spanning tree : 13
     */