fork(1) download
copy 
  1. import java.util.ArrayList;
  2. import java.util.Collections;
  3. import java.util.Comparator;
  4. import java.util.HashMap;
  5. import java.util.LinkedList;
  6. import java.util.List;
  7. import java.util.Scanner;
  8. import java.util.Stack;
  9.  
  10. class KaushikKruskalAlgorithm 
  11. {
  12.     private List<Edge> edges;
  13.     private int numberOfVertices;
  14.     public static final int MAX_VALUE = 999;
  15.  
  16.     public KaushikKruskalAlgorithm(int numberOfVertices)
  17.     {
  18.         this.numberOfVertices = numberOfVertices;
  19.         edges = new LinkedList<Edge>();
  20.     }
  21.  
  22.     public void kruskalAlgorithm()
  23.     {
  24.     	HashMap<Integer,Boolean> vistedNodes = new HashMap<Integer,Boolean>();
  25.     	List<Edge> selectedEdges = new ArrayList<Edge>();
  26.         boolean finished = false;
  27.        // Collections.sort(edges, new EdgeComparator());
  28.         Collections.sort(edges);
  29.         for (Edge edge : edges)
  30.         {
  31.             if (vistedNodes.get(edge.sourcevertex)==null || vistedNodes.get(edge.destinationvertex)==null){
  32.             	// Either of node is not covered. So use this edge
  33.             	selectedEdges.add(edge);
  34.             	vistedNodes.put(edge.sourcevertex, Boolean.TRUE);
  35.             	vistedNodes.put(edge.destinationvertex, Boolean.TRUE);
  36.             }
  37.         }
  38.         System.out.println("The spanning tree is ");
  39.         for (Edge edge : selectedEdges){
  40.         	System.out.println("Between node "+edge.sourcevertex +" & node "+edge.destinationvertex +" weight "+edge.weight);
  41.         }
  42.     }
  43.  
  44.     public static void main (String[] args)
  45.     {	
  46.         int adjacency_matrix[][];
  47.         int number_of_vertices;
  48.  
  49.         Scanner scan = new Scanner(System.in);
  50.         System.out.println("Enter the number of vertices");
  51.         number_of_vertices = scan.nextInt();
  52.         adjacency_matrix = new int[number_of_vertices + 1][number_of_vertices + 1];
  53.         KaushikKruskalAlgorithm kruskalAlgorithm = new KaushikKruskalAlgorithm(number_of_vertices);
  54.  
  55.         for (int i = 1; i <= number_of_vertices; i++)
  56.         {
  57.             for (int j = i+1; j <= number_of_vertices; j++)
  58.             {
  59.             	System.out.println("Enter distance between node "+ i +" and "+j);
  60.                 int weight = scan.nextInt();
  61.                 if(weight!=0){
  62.                     Edge edge = new Edge(); 
  63.                     edge.sourcevertex = i;
  64.                     edge.destinationvertex = j;
  65.                     edge.weight = weight;
  66.                     kruskalAlgorithm.edges.add(edge);
  67.                 }
  68.             }
  69.         }
  70.         kruskalAlgorithm.kruskalAlgorithm();
  71.         scan.close();
  72.     }
  73.  
  74.  
  75.  
  76.  }
  77.  
  78.  class Edge implements Comparable<Edge>
  79.     {
  80.         int sourcevertex;
  81.         int destinationvertex;
  82.         int weight;
  83.  
  84.         @Override
  85.         public int compareTo(Edge edge2) {
  86.             if (this.weight < edge2.weight)
  87.                 return -1;
  88.             if (this.weight > edge2.weight)
  89.                 return 1;
  90.             return 0;
  91.         }
  92.  
  93.     }
  94.  
Runtime error #stdin #stdout #stderr 0.1s 380736KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Enter the number of vertices
stderr
copy 
Exception in thread "main" java.util.NoSuchElementException
	at java.util.Scanner.throwFor(Scanner.java:907)
	at java.util.Scanner.next(Scanner.java:1530)
	at java.util.Scanner.nextInt(Scanner.java:2160)
	at java.util.Scanner.nextInt(Scanner.java:2119)
	at KaushikKruskalAlgorithm.main(Main.java:51)
https://ideone.com/IdwASw
language:
Java (HotSpot 12)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!