# Content

• 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

# 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.

# 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.

# Implementation(Code Java)

import java.util.*;

# 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.

--

--