Kruskal Algorithm

import java.util.*;

class Edge
{
  int  v1,v2,w;
}
class Graph
{
  Edge edge[];
  int v,e;
  int p[];

  void creategraph()
  {
    int a,b,w;

    Scanner kbd = new Scanner(System.in);
    System.out.print("Enter number of vertices ");
    v = kbd.nextInt();
    System.out.print("Enter number of edges ");
    e = kbd.nextInt();
    edge = new Edge[e+1];
    for (int i = 1 ; i <= e ; i++)
      edge[i] = new Edge();
    for (int i = 1; i<= e ; i++)
    {
      System.out.print("Enter edge information ");
      a = kbd.nextInt();
      b = kbd.nextInt();
      System.out.print("Enter weight of this edge ");
      w = kbd.nextInt();
      edge[i].v1 =  a;
      edge[i].v2 =  b;
      edge[i].w =  w;
    }

  } // end creategraph

  void bubble()
  {
    for (int i = e-1 ; i >= 1 ; i--)
     for (int j = 1 ; j <= i ; j++)
      if (edge[j].w > edge[j+1].w)
      {
        Edge t = edge[j];
        edge[j] = edge[j+1];
        edge[j+1] = t;
      }
  }

  int find(int z) // find parent of z
  {
    while (p[z] != -1)
     z = p[z];

    return z;
  }
  void union(int u , int v)
  {
    p[v] = u;
  }
  void kruskal()
  {
   p = new int[v+1];
     for(int i = 1 ; i <= v  ; i++)
      p[i] = -1;
    int  mincost = 0 ;
    int  noofedgesadded = 0;
    for (int i = 1 ; i <= e && noofedgesadded != v-1 ; i++)
    {
      Edge t = edge[i];

      int start = t.v1;
      int end = t.v2;

      int p1 = find(start);
      int p2 = find(end);

      if (p1 != p2)
      {
        mincost += t.w;
        System.out.println("Vertex " + start + " to vertex " + end);
        union(p1,p2);
        noofedgesadded++;
       
      }
    } // for loop

    System.out.println("minimum cost = " + mincost);

  } // end of kruskal

} //end Graph class

public class Kruskal
{
  public static void main(String args[])
  {
    Graph g = new Graph();
    g.creategraph();
    g.bubble();
    g.kruskal();
  }
}
/*
 Output:
 Enter number of vertices 6
Enter number of edges 11
Enter edge information
1
2
Enter weight of this edge 2
Enter edge information 1
3
Enter weight of this edge 2
Enter edge information 1
6
Enter weight of this edge 6
Enter edge information 1
4
Enter weight of this edge 18
Enter edge information 2
4
Enter weight of this edge 7
Enter edge information 4
3
Enter weight of this edge 3
Enter edge information 6
5
Enter weight of this edge 5
Enter edge information 3
6
Enter weight of this edge 8
Enter edge information 3
5
Enter weight of this edge 4
Enter edge information 4
5
Enter weight of this edge 9
Enter edge information 2
3
Enter weight of this edge 1
Vertex 2 to vertex 3
Vertex 1 to vertex 2
Vertex 4 to vertex 3
Vertex 3 to vertex 5
Vertex 6 to vertex 5
minimum cost = 15
Process completed.*/