Posts Minimal Spanning Tree
Post
Cancel

Minimal Spanning Tree

Problem Description

Given a weighted, undirected and connected graph of V vertices and E edges. The task is to find the sum of weights of the edges of the Minimum Spanning Tree.

geeksforgeeks

Solution

Here we have used Kruskal’s algorithm.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class Solution{
    
 static int spanningTree(int V, int E, int edges[][]){
     
     //sort based on weight of the edges (ascending)
     //this is obvious because we need to form a tree which min weight
     Arrays.sort(edges, (o1, o2) -> o1[2] > o2[2]?1: (o1[2] < o2[2]?-1:0));
     
     //init parent array -> initially with no edges, every node will be its own parent
     int[] parent = new int[V];
     for(int i=0; i<parent.length; i++){
         parent[i] = i;
     }
     
     //init total cost
     int cost = 0;
     
     //check for each edge if it can be included
     for(int i=0; i<E; i++){
         
         //get the nodes forming the current edge
         int u = edges[i][0];
         int v = edges[i][1];
         
         //if both the nodes are part of the same connected component, we cannot choose it as they will form a cycle if included
         //if they have different leaders, they can be merged as a single component. pick that edge and add the cost
         if(union(u, v, parent)){
             cost += edges[i][2];
         }
         
     }
     
     return cost;
     
 }
 
 public static int find(int x, int[] parent){
     
     while(parent[x] != x){
         x = parent[x];
     }
     
     return parent[x];
     
 }
 
 public static boolean union(int x, int y, int[] parent){
     
     //if parent of x and y are same, union is not needed so return false
     if(find(x, parent) == find(y, parent)) return false;
     
     //else, merge them and return true
     //to merge them, we need to change the parent of the leader of one component as the leader of second component
     parent[find(x, parent)] = find(y, parent);
     
     return true;
     
 }
 
}

Optimization

In the previous code, find(node) method which gets the leader of any node can take O(height of tree) => O(N) in the worst case. If we could somehow reduce the height of the tree, that would help in reducing the time taken to get the leader. While finding the leader, we can keep changing the leaders of intermediate nodes in such a way that they directly point to the leader of that connected component. So the next time we try to find the leader, it will take O(1) time. The only change will be in the find(node) method -

1
2
3
4
5
6
7
8
9
10
11
12
13
 public static int find(int x, int[] parent){
    
    //if parent of x is x, then return it
    if(parent[x] == x){
        return parent[x];
    }
    
    //else update it's parent so point to the leader directly
    parent[x] = find(parent[x], parent);
    
    //return updated parent[x]
    return parent[x];
 }
This post is licensed under CC BY 4.0 by the author.