Apr 11
Critical Review (Kruskal’s Algorithm)
In this section, I’ve looked at What is Kruskla’s Algorithm?, its Time Complexity, Parallelism, and Real-World Applications. I’ve also spoken about how we can use Parallel Algorithm and Helper Thread function to reduce the overall complexity of Kruskal’s Algorithm.
Content
- What’s Kruskla’s Algorithm?
- Mathematical Expression
- Activity Diagram
- Time Complexity
- What is Parallelizing in Algorithm?
- Parallelizing in Kruskal’s Algorithm
- Impact of Parallelization on Kruskal’s Algorithm
- Implementation of Kruskal’s Algorithm (Java)
- Real Life Application of Kruskal’s Algorithm
What’s Kruskal’s Algorithm?
For a connected weighted graph, Kruskal’s Algorithm is used to determine the minimum spanning tree. The algorithm’s main task is to identify a subset of edges that can be used to visit every node of the graph.
Mathematical Expression for Kruskal’s Algorithm
Let G = (V,E) be a connected graph with V ={1,….,n} and let w:E→ R be a weight function on G. We assume that E is given as a list of edges.
Procedure KRUSKAL (G, w;T)
T ← Ø
I =1 to n do Vi ← {i} od;
Put E into a priority queue Q with priority function w;
While Q = Ø do
e:= determine (Q);
Find the end vertices u and v of e;
Find the components Vu and Vv containing u and v , respectively ;
If Vu ≠ Vv then Merge(Vu,Vv); T ←T U{e} fi
Od
Activity Diagram for Kruskal’s algorithm
Time and Space Complexity of Kruskal’s Algorithm
I used the letters ‘V’ and ‘E’ to represent vertices and edges in order to compute the time complexity of Kruskal’s Algorithm.
So, in order to solve Kruskal’s algorithm, we used an input array (Edge type , refer the Code mentioned at the bottom) with a size of ‘E’.
We sorted the input array in ascending order of their weights in the next phase, so it took ElogE time to sort that array.
Finally, we must add edges to the MST while ensuring that it does not form a cycle, which will take EV time.
Therefore the overall time complexity of Kruskal’s Algorithm is O(ElogE+VE).
Disjoint Set Data Structure involves O(|V|) space to keep track of the roots of all vertices and another O(|E|) space to store all edges in a sorted fashion, resulting in a space complexity of O(|E| + |V|.
What is Parallel Algorithm?
A parallel algorithm is one that can run several instructions on different processing devices simultaneously and then combine all of them to get the final result.
Parallelizing Kruskal’s algorithm and Its Impact
Kruskal’s algorithm is serial by definition. It does, however, have a characteristic that can be used to derive parallelism. More precisely, if an edge that will be investigated in a future iteration is determined to already form a cycle within the MSF constructed up to this iteration, it can be safely dismissed at this time. This trait effectively permits edges to be rejected out of sequence.
To make use of the above mentioned property, I can create and then use a helper thread function whose purpose is to run the regular, sequential Kruskal’s algorithm and examine the edge with the next lowest weight at every iteration.
Simultaneously with the main thread, a number of auxiliary threads analyze edges of greater weight, assessing if they would create a cycle if added to the present MSF. The matching edge is marked as discarded once a cycle is discovered. Because these edges have been safely omitted from the MSF, the main thread only needs to check the edges that were not rejected by the auxiliary threads, resulting in a faster implementation than the sequential approach. The more cycles detected by the helper threads, the more unloading the main thread will obtain.
Implementation(Code Java)
import java.util.*;
class Edge implements Comparable<Edge>{
int source;
int destination;
int weight;
@Override
public int compareTo(Edge o) {
return this.weight — o.weight;
}}
public class kruskals_graph {
public static int findParent(int v,int parent[]) {
if(parent[v] == v) {
return v;
}
return findParent(parent[v],parent);
}
public static void kruskals(Edge input[] , int n) {
Arrays.sort(input);
Edge output[] = new Edge[n-1];
// Parent array
int parent[] = new int[n];
for(int i =0;i < n;i++) {
parent[i] =i;
}
int count =0;
int i =0;
while(count != n-1) {
Edge currentEdge = input[i];
int sourceparent = findParent(currentEdge.source,parent);
int destinationparent = findParent(currentEdge.destination,parent);
if(sourceparent != destinationparent) {
output[count] = currentEdge;
count++;
parent[sourceparent] = destinationparent;
}
i++;
}
// Printing the elements
for(int j =0 ;j < n-1;j++) {
if(output[j].source < output[j].destination) {
System.out.println(output[j].source+” “+output[j].destination+” “+output[j].weight);
}
else {
System.out.println(output[j].destination+” “+output[j].source+” “+output[j].weight);
}}}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println(“Enter the vertex”);
int n = sc.nextInt();
System.out.println(“Enter the edge”);
int e = sc.nextInt();
Edge input[] = new Edge[e];
for(int i =0; i < e;i++) {
input[i] = new Edge();
input[i].source = sc.nextInt();
input[i].destination = sc.nextInt();
input[i].weight = sc.nextInt();
}
kruskals(input,n);
}}
Real Life Application of Kruskal’s Algorithm
The Disjoint Set Union data structure in Kruskal’s method is used by the preponderance of cable network operators to discover the quickest way to install wires across a city or set of cities.
Please visit my other blogs : https://samarthsharmaagrasabby.medium.com/minimum-spanning-tree-efc10bd4710a
https://samarthsharmaagrasabby.medium.com/print-on-demand-b8f795d60341
