Kruskal MST is find a tree with minimum weight and connect all the vertex of graph.
A minimum spanning tree has (V – 1) edges where V is the number of vertices in the given graph.
Steps:
1.Get all edges of graph
2.sort all edges by weight in ascending order
3.pick all edges in loop one by one
a.get vertex of edge
b.find root of both vertex using disjoint set algo
c.if both vertex root is same then continue otherwise
d.add into result list and do union of both vertex using disjoint set.
public class KruskalMST {
public static class EdgeComparator implements Comparator<Graph<Integer>.Edge<Integer>> {
@Override
public int compare(Graph<Integer>.Edge<Integer> t1, Graph<Integer>.Edge<Integer> t2) {
return t2.weight >= t1.weight ? -1 : 0;
}
}
public List<Graph<Integer>.Edge<Integer>> mst(List<Graph<Integer>.Edge<Integer>> list, Collection<Graph<Integer>.Vertex<Integer>> vertexList){
Collections.sort(list,new EdgeComparator());
DisjointSet disjointSet = new DisjointSet();
for(Graph<Integer>.Vertex<Integer> vertex: vertexList){
disjointSet.make((int)vertex.id);
}
List<Graph<Integer>.Edge<Integer>> result = new ArrayList<>();
for(Graph<Integer>.Edge<Integer> edge: list){
int root1 = disjointSet.findSet((int)edge.v1.id);
int root2 = disjointSet.findSet((int)edge.v2.id);
if(root1==root2){
continue;
}
else{
result.add(edge);
disjointSet.union((int)edge.v1.id,(int)edge.v2.id);
}
}
return result;
}
public static void main(String[] args) {
Graph<Integer> graph = new Graph<Integer>(false);
graph.addEdge(1, 2, 4);
graph.addEdge(1, 3, 1);
graph.addEdge(2, 5, 1);
graph.addEdge(2, 6, 3);
graph.addEdge(2, 4, 2);
graph.addEdge(6, 5, 2);
graph.addEdge(6, 4, 3);
graph.addEdge(4, 7, 2);
graph.addEdge(3, 4, 5);
graph.addEdge(3, 7, 8);
System.out.println(graph);
List<Graph<Integer>.Edge<Integer>> list = graph.getAllEdges();
KruskalMST kruskalMST = new KruskalMST();
list = kruskalMST.mst(list,graph.getAllVertex());
for(Graph<Integer>.Edge<Integer> e: list){
System.out.print("vertex:"+e.getV1().id);
System.out.println(" vertex: "+e.getV2().id);
System.out.println("weight:"+e.getWeight());
System.out.println("*******");
}
}
}
output:
vertex:2 vertex: 5
weight:1
*******
vertex:1 vertex: 3
weight:1
*******
vertex:4 vertex: 7
weight:2
*******
vertex:6 vertex: 5
weight:2
*******
vertex:2 vertex: 4
weight:2
*******
vertex:1 vertex: 2
weight:4
*******
Graph Class:
public class Graph<T> {
private List<Edge<T>> allEdges;
private Map<Long,Vertex<T>> allVertex;
private boolean isDirected;
Graph(boolean isDirected){
this.isDirected = isDirected;
allEdges = new ArrayList<>();
allVertex = new HashMap<>();
}
void addEdge(long v1, long v2, int weight){
Vertex<T> vertex1 = null;
if(allVertex.containsKey(v1)){
vertex1 = allVertex.get(v1);
}else{
vertex1 = new Vertex<>( v1);
allVertex.put(v1,vertex1);
}
Vertex<T> vertex2 = null;
if(allVertex.containsKey(v2)){
vertex2 = allVertex.get(v2);
}else{
vertex2 = new Vertex<>( v2);
allVertex.put(v2,vertex2);
}
Edge edge = new Edge(vertex1,vertex2,isDirected,weight);
if(!allEdges.contains(edge)){
allEdges.add(edge);
}
vertex1.addAdjecent(edge);
if(!isDirected){
vertex2.addAdjecent(edge);
}
}
public List<Edge<T>> getAllEdges(){
return allEdges;
}
public Collection<Vertex<T>> getAllVertex(){
return allVertex.values();
}
class Edge<T>{
Vertex<T> v1;
Vertex<T> v2;
boolean isDirected;
int weight;
Edge(Vertex v1, Vertex v2, boolean isDirected, int weight){
this.v1 = v1;
this.v2 = v2;
this.isDirected = isDirected;
this.weight = weight;
}
public Vertex<T> getV1() {
return v1;
}
public void setV1(Vertex<T> v1) {
this.v1 = v1;
}
public Vertex<T> getV2() {
return v2;
}
public void setV2(Vertex<T> v2) {
this.v2 = v2;
}
public boolean isDirected() {
return isDirected;
}
public void setDirected(boolean directed) {
isDirected = directed;
}
public int getWeight() {
return weight;
}
public void setWeight(int weight) {
this.weight = weight;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Edge<?> edge = (Edge<?>) o;
return Objects.equals(v1, edge.v1) &&
Objects.equals(v2, edge.v2);
}
@Override
public int hashCode() {
return Objects.hash(v1, v2);
}
}
class Vertex<T>{
long id;
T data;
List<Edge<T>> allAdjecent;
void addAdjecent(Edge<T> edge){
allAdjecent.add(edge);
}
Vertex(long id){
this.id = id;
allAdjecent = new ArrayList<>();
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Vertex<?> vertex = (Vertex<?>) o;
return id == vertex.id;
}
@Override
public int hashCode() {
return Objects.hash(id);
}
}
}
DisjointSet :
public class DisjointSet {
Map<Integer,Node> map = new HashMap<>();
class Node{
int rank;
int data;
Node parent;
}
Node make(int val){
Node node = new Node();
node.data = val;
node.rank = 0;
node.parent = node;
map.put(val,node);
return node;
}
boolean union(int n1, int n2){
Node node1 = map.get(n1);
Node node2 = map.get(n2);
Node parent1 = findSet(node1);
Node parent2 = findSet(node2);
if(parent1.data==parent2.data){
return false;
}
if(parent1.rank>=parent2.rank){
parent1.rank = (parent1.rank==parent2.rank)? parent1.rank+1:parent1.rank;
parent2.parent = parent1;
}else {
parent1.parent = parent2;
}
return true;
}
Node findSet(Node node){
Node parent = node.parent;
if(node==parent){
return parent;
}else{
node.parent = findSet(node.parent);
}
return node.parent;
}
int findSet(int val){
return findSet(map.get(val)).data;
}
public static void main(String[] args) {
DisjointSet ds= new DisjointSet();
ds.make(1);
ds.make(2);
ds.make(3);
ds.make(4);
ds.make(5);
ds.make(6);
ds.make(7);
ds.union(1, 2);
ds.union(2, 3);
ds.union(4, 5);
ds.union(6, 7);
ds.union(5, 6);
ds.union(3, 7);
System.out.println(ds.findSet(1));
System.out.println(ds.findSet(2));
System.out.println(ds.findSet(3));
System.out.println(ds.findSet(4));
System.out.println(ds.findSet(5));
System.out.println(ds.findSet(6));
System.out.println(ds.findSet(7));
}
}
output:
