Basic Code Snippet for "Kruskal's Minimum Spanning Tree Algorithm" in java.
Mihir_Mehta
464
Graph TheoryMinimum Spanning TreeCareer

Problem statement -

  1. There are n cities from 1 to n.
  2. Given an array of connections
    where " connections[i] = [ xi, yi, costi ] " indicates that the cost of connecting city xi and city yi (bidirectional connection) is costi.

Return the minimum cost to connect all the n cities such that there is at least one path between each pair of cities. If it is impossible to connect all the n cities, return -1
One of the solutions to the above problem is - " Kruskal's Minimum Spanning Tree Algorithm
"
A Minimum Spanning Tree (MST) is a tree in a weighted undirected graph that connects all the vertices with minimum total weight. In other words, it is a subset of edges that forms a tree and connects all the vertices in the graph such that the sum of the edge weights is minimized.

For understanding "union find" concept

https://leetcode.com/discuss/study-guide/2006177/basic-code-snippet-for-union-finddisjoint-set-data-structure-in-java

ref:

class UnionFind {

int n; // n = no of vertices / cities
int[] root;

public UnionFind(int n){
    this.n=n;
    root= new int[n];
    for(int i=1;i<n;i++){
        root[i]=i;
    }
}

public void union(int x, int y){
    int rootX=find(x);
    int rootY=find(y);
    
    if(rootX != rootY){
        root[rootY]=rootX;
    }
}

public int find(int x){
    if(root[x] == x)
        return x;
    
    return root[x]=find(root[x]);
}

public boolean isConnected(int x, int y){
    return find(x) == find(y);
}

}

class Solution {

// kruskal is an algorithm that use the least weighted edge to connect to unconnected nodes
// leverage union-find

public int minimumCost(int n, int[][] connections) {
    UnionFind uf= new UnionFind(n+1);
    
    // sort the cities / edges based on increasing order of cost
    // this will convert problem into kruskal algo kind of requirement for finding minimum spanning tree
    Arrays.sort(connections, (a,b) -> a[2] - b[2]);
    
    int cntEdges=0;
    int cost=0;
    for(int i=0;i<connections.length;i++){
        int x=connections[i][0];
        int y=connections[i][1];
        
        if(!(uf.isConnected(x,y))){
            uf.union(x,y);
            cost+=connections[i][2];
            cntEdges++;
        }
        
    }
    
    if(cntEdges == n-1){
        return cost;
    }else{
        return -1;
    }
    
}

}

Comments (0)