Critical Review (Kruskal’s Algorithm)

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

What’s 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.

Activity Diagram for Kruskal’s algorithm

Activity Diagram

Time and Space Complexity of Kruskal’s Algorithm

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.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store