Question: Write a program to find the minimum cost of connecting all the engineering colleges in
your state using Kruskal's algorithm.
Code:
Code:
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
public class Kruskal {
static class edge{
int distance,s,d;
public edge(int distance, int s, int d) {
this.distance = distance;
this.s = s;
this.d = d;
}
@Override public String toString() {
return "edge{" +
"distance=" + distance +
", s=" + s +
", d=" + d +
'}';
}
}
public static void main(String[] nt){
int graph[][]= {{0, 2, 0, 6, 0},
{2, 0, 3, 8, 5},
{0, 3, 0, 0, 7},
{6, 8, 0, 0, 9},
{0, 5, 7, 9, 0},
};
boolean[] visited=new boolean[graph.length];
ArrayList<edge>edgeArrayList=new ArrayList<>();
for(int i=0;i<graph.length;i++){
visited[i]=false;
for(int x=0;x<graph[i].length;x++){
if(graph[i][x]!=0){
edgeArrayList.add(new edge(graph[i][x],i,x));
}
}
}
Collections.sort(edgeArrayList, new Comparator<edge>() {
@Override public int compare(edge edge, edge t1) {
return edge.distance-t1.distance;
}
});
int count=0;
edge edgenow;
int min=0;
while (count!=graph.length-1){
edgenow=edgeArrayList.get(0);
edgeArrayList.remove(0);
if(visited[edgenow.d]==false || visited[edgenow.s]==false){
min+=edgenow.distance;
System.out.println((edgenow.s+1)+" -> "+(edgenow.d+1)+" : "+edgenow.distance);
visited[edgenow.d]=true;
visited[edgenow.s]=true;
count++;
}
}
System.out.println("Cost is : "+min);
}
}
Output:
