package Algorithm;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Comparator;
public class Kruskal {
int vertex;
ArrayList<Edge> graph = new ArrayList<>();
public ArrayList<Edge> getGraph() {
return graph;
}
public void setGraph(ArrayList<Edge> graph) {
this.graph = graph;
}
public int getVertex() {
return vertex;
}
public void setVertex(int vertex) {
this.vertex = vertex;
}
public void minSpaningTree() {
int[] parentSet = new int[vertex];
int sum = 0;
int n,m;
//sort the edge
graph.sort(new Comparator<Edge>() {
@Override
public int compare(Edge o1, Edge o2) {
// TODO Auto-generated method stub
return o1.getWeight()-o2.getWeight();
}
});
for(int i =0;i<graph.size();i++) {
Edge edge= graph.get(i);
n=Disjoint(parentSet, edge.getBegin());
m=Disjoint(parentSet, edge.getEnd());
if(n!=m) {
parentSet[n]=m;
System.out.println(edge.getBegin()+" "+edge.getEnd()+" "+edge.getWeight());
sum = sum+edge.getWeight();
}
}
System.out.println("sum:"+sum);
}
public int Disjoint(int[] parentSet,int vertex1) {
while(parentSet[vertex1]>0) {
vertex1 =parentSet[vertex1];
}
return vertex1;
}
public static void main(String[] args) {
Kruskal k =new Kruskal();
ArrayList<Edge> graph=new ArrayList<>();
graph.add(new Edge(0, 1, 2));
graph.add(new Edge(1, 2, 3));
graph.add(new Edge(2, 0, 2));
graph.add(new Edge(2, 3, 4));
k.setGraph(graph);
k.setVertex(4);
k.minSpaningTree();
}
}
