Minimum Spanning Tree - Kruskal's Algorithm

 Click Me


What is Minimum Spanning Tree (MST)?
  • A Minimum Spanning Tree (MST) is a subset of the edges of a connected, undirected and weighted graph. Thus MST is a tree.
  • MST connects all the vertices/nodes of the graph together. 
  • MST does not contain any cycles.
  • MST finds minimum edge weight.
  • MST contains (V-1) edges, where V is the number of vertices/nodes in the graph. 
  • No. of Spanning Trees possible for a graph (caution: Here I am not talking about Minimum Spanning Tree, but Spanning Tree in general): [ |E|C|V-1| ] - [no. of cycles]       ( here C is Combination of pnc) 
  • Kruskal's Algorithm uses a Disjoint Set Data Structure to find Minimum Spanning Tree.
  • Kruskal's Algorithm is a greedy algorithm.
 
Kruskal's Algorithm
1. for each node perform makeSet() operation of disjoint set
2. sort each edge of the graph in non-decreasing order by weight 
3. for each edge (u,v):
        4. if findSet(u) != findSet(v)  [This means if parent/representative of two disjoint sets is different]
                    5.  perform union(u,v) operation of disjoint set
                    6.  update minWeightEdge += weight of edge(u,v)
        7. else if findSet(u) == findSet(v)   [This means if parent/representative of two disjoint sets is same]
                    8. this means we have a cycle if we include edge(u,v) in our MST. so we skip this edge.


Code:

import java.util.*;

// The Graph Node
class GraphNode{
    String data;
    // adjacent nodes
    ArrayList<GraphNode> neighbours;
    // weight od edges connecting this node to it's adjacent nodes
    HashMap<GraphNode,Integer> weightMap;
    
    // Constructor
    GraphNode(String x){
        this.data = x;
        this.neighbours = new ArrayList<>();
        this.weightMap = new HashMap<>();
    }
    
}


// class representing an undirected weighted edge between two nodes: 'firstNode' and 'secondNode'
class UndirectedEdge{
    GraphNode firstNode;
    GraphNode secondNode;
    // weight of edge
    int weight;
    
    // constructor
    UndirectedEdge(GraphNode x, GraphNode y, int wt){
        this.firstNode = x;
        this.secondNode = y;
        this.weight = wt;
    }
}

// class to represent a disjoint set containing a graph node
class DisjointSet{
    GraphNode node;
    // rank of this disjont set
    int rank;
    // parent/representative of this disjoint set
    DisjointSet parent;
    
    // constructor
    DisjointSet(GraphNode node){
        this.node = node;
        this.rank = 1;
        this.parent = null;
    }
}


public class Main {
    
    // list to store all nodes
    ArrayList<GraphNode> nodesList;
    // list to store all edges in the graph
    ArrayList<UndirectedEdge> edgesList;
    // a hashmap that to get the disjoint set associated with a graphnode
    HashMap<GraphNode,DisjointSet> nodeDisjointSetMap;
    
    // constructor
    Main(){
        this.nodesList = new ArrayList<>();
        this.edgesList = new ArrayList<>();
        this.nodeDisjointSetMap = new HashMap<>();
    }
    
    // method to add an undirected weighted edge between nodes at index i and j of nodesList
    public void addUndirectedWeightedEdge(int i, int j, int weight){
        GraphNode node1 = this.nodesList.get(i);
        GraphNode node2 = this.nodesList.get(j);
        
        // adding node 2 in neighbours of node1
        node1.neighbours.add(node2);
        // adding node2 with weight in the weightmap of node 1
        node1.weightMap.put(node2,weight);
        
        // similarly for node 2 as well
        node2.neighbours.add(node1);
        node2.weightMap.put(node1,weight);
        
        // adding the newly created edge into the edge list too
        this.edgesList.add(new UndirectedEdge(node1,node2,weight));
    }
    
    // method to sort th undirected Weighted edges in edgesList on the basis of weight in non-decreasing order
    // this is done to ensure that we pick the least cost/weight edges for out minimum spanning tree.
    public void sortUndirectedEdgesByWeight(){
        // we have to provide a comparator and overload the compareTo method  to sort the arraylist containing 'UndirectedEdge'
        Comparator<UndirectedEdge> comparator = new Comparator<UndirectedEdge>() {
@Override
public int compare(UndirectedEdge o1, UndirectedEdge o2) {
return o1.weight - o2.weight;
}
};
// finally sorting the edgesList on the basis of edge weight with the help of comparator
Collections.sort(this.edgesList, comparator);
    }
    
    // method to do makeset operation of disjoint set
    public void makeSet(){
        for(int i=0;i<this.nodesList.size();i++){
            DisjointSet disJointSet = new DisjointSet(this.nodesList.get(i));
            disJointSet.parent = disJointSet;
            nodeDisjointSetMap.put(this.nodesList.get(i),disJointSet);
        }
    }
    
    // mehod to implement find set method of disjoint set using path compression
    public DisjointSet find(DisjointSet node){
        DisjointSet parent = node.parent;
        if(parent==node){
            return parent;
        }
        else{
            parent = find(parent);
        }
        node.parent = parent;
        return parent;
    }
    
    // method to find the union of two disjoint sets
    public int union(DisjointSet node1Set, DisjointSet node2Set){
        DisjointSet parentNode1 = find(node1Set);
        DisjointSet parentNode2 = find(node2Set);
        
        // if same parent
        if(parentNode1==parentNode2){
            // returning -1 indicates we have encountered a cycle
            return -1;
        }
        
        // if parents/representatives are different for both disjoint sets
        if(parentNode1.rank>=parentNode2.rank){
            parentNode1.rank = parentNode1.rank + parentNode2.rank;
            parentNode2.parent = parentNode1;
        }
        else{
            parentNode2.rank = parentNode2.rank + parentNode1.rank;
            parentNode1.parent = parentNode2;
        }
        
        return 0;
    }
    
    // method to implement Kruskal Algorithm to find Minimum Spanning Tree (MST)
    public void kruskal(){
        makeSet();
        sortUndirectedEdgesByWeight();
        
        int totalWeight = 0;
        
        // for each edge in the graph
        for(int i=0;i<edgesList.size();i++){
            UndirectedEdge currentEdge = this.edgesList.get(i);
            GraphNode node1 = currentEdge.firstNode;
            GraphNode node2 = currentEdge.secondNode;
            
            DisjointSet node1Set = this.nodeDisjointSetMap.get(node1);
            DisjointSet node2Set = this.nodeDisjointSetMap.get(node2);
            
            
            int unionSet = union(node1Set,node2Set);
            // if cycle exits
            if(unionSet==-1){
                continue;
            }
            else{
                System.out.println("Edge: " + node1.data + "------" + node2.data +"   || weight= " + currentEdge.weight);
                totalWeight += currentEdge.weight;
            }
        }
        
        System.out.println("Total weight of MST: " + totalWeight);
    }
    
    public static void main(String[] args) throws Exception {
        Main graph = new Main();
        
        // adding vertices/nodes
        for(int i=0;i<4;i++){
            graph.nodesList.add(new GraphNode("V"+i));
        }
        
        // adding undirected, weighted edges 
        graph.addUndirectedWeightedEdge(0,1,10);
        graph.addUndirectedWeightedEdge(1,3,15);
        graph.addUndirectedWeightedEdge(3,2,4);
        graph.addUndirectedWeightedEdge(2,0,6);
        graph.addUndirectedWeightedEdge(3,0,5);
        
        graph.kruskal();
        
    }
}

Output:

Edge: V3------V2   || weight= 4
Edge: V3------V0   || weight= 5
Edge: V0------V1   || weight= 10
Total weight of MST: 19

Comments

Post a Comment

Popular posts from this blog

Binary Heap - Introduction

Image
#Image Credit - GeeksForGeeks Types of heap: Min Heap - every node is less than or equal to  its children(s) Max Heap - every node is more than or equal to its children(s) Operations on any heap : create insert extract/delete - we can extract/delete only the top node in any heap traverse delete entire heap get size of heap peek top of heap We should prefer implementing binary heap using arrays and not linked list, as during bottom to top heapify, in reaching the bottom rightmost node we take only 0(1) time in case of array but we take 0(n) time in case of linked list because first, we need to level order traverse the binary heap tree to get bottom-most rightmost element.  Heaps are used to efficiently implement:  Prim's Algorithm Heapsort Priority queue
Read more

Divide and Conquer - Introduction

Image
What is Divide and Conquer? Divide and Conquer is an algorithm paradigm in which we break down a given problem into smaller sub-problems of similar type until the sub-problems are small enough to be solved directly. The solution to these sub-problems are then combined to give a solution to the original problem.  Study the diagram below, it will then make more sense about what we do in Divide and Conquer : Where to Apply Divide and Conquer? The Divide and Conquer can be applied to all those problems that show Optimal Substructure property.  So, What is this Optimal Substructure property now? If we can break down a problem into similar sub-problems and the solution of these sub-problems can be used to create the solution of the whole problem, then that problem is said to have the Optimal Substructure property. For eg. : Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2),    In this example, we can see that if we want to find the Fibonacci number at the nth place, we can br...
Read more

Bubble Sort

Time complexity - O(n^2)  || Space Complexity - O(1) Bubble sort is an inplace sorting algorithm, that means we do not any extra space while bubble sorting public class Main {     public static void main(String[] args) throws Exception {         int[] arr={1,4,4,5,6,2,3,90,120,43,0};                  System.out.println("UnSorted Array :");         for(int i=0;i<arr.length;i++){             System.out.print(arr[i]+" ");         }         System.out.println();         // bubble sort         for(int i=0;i<arr.length-1;i++){ // iterates through first to last cell             for(int j=0;j<arr.length-1-i;j++){ // inner loop controls swapping and extent to which swapping is to be performed in array     ...
Read more