Minimum Spanning Tree using Kruskal’s and Prim’s Algorithms

4 min readAug 22, 2021

To understand the minimum spanning tree, you have to start by understanding the undirected cyclic graph. A cycle graph consists of vertices and edges; all the edges are connected forming a cycle. This graph is used to construct multiple spanning trees.

What is a spanning tree?

A spanning tree is a subset of the original tree, in this case, Graph G. All the vertices in a spanning tree are connected forming an acyclic graph. Every undirected and connected graph has at least one spanning tree.

Properties of Spanning Tree

Undirected graph G=(V, E).
A spanning tree has the same number of vertices as the original graph.
The number of edges (E) in a spanning tree is one less than the number of vertices (V). E = |V| — 1
The graph must be connected, with no cycle.
A complete undirected graph can have n^(n-2) number of spanning trees. n^n(n — 2) = 3^(3-2) = 3

Minimum Spanning Tree

Of all the spanning trees, the one with lights total edge weights is the minimum spanning tree. There are two methods to find Minimum Spanning Tree:

Kruskal’s Algorithm
Prim’s Algorithm

Kruskal’s Algorithm

Kruskal’s algorithm is a greedy algorithm used to find the minimum spanning tree of an undirected graph in increasing order of edge weights.

Steps:

Arrange all the edges E in non-decreasing order of weights
Find the smallest edges and if the edges don’t form a cycle include it, else disregard it.
Repeat the 2nd step until you reach v-1 edges.

Pseudocode

MST-KRUSKAL(G, w )   // A is initally empty, it will store all the edges of the MST
   A = {}  // for each vertex of the graph make a disjoint-set with that   vertex   for each vertex v ∈ G.V
       MAKE-SET(v)                  // O(V)   sort the edges of G.E           //into increasing order by weight                                   
                                   //O(E log E)   // for each set that connects u & v , the smallest edge will be used first     forEach edge (u, v) ∈ G.E     //increaing order; O(V log V)        //if set of u (v1) doesn’t equal to v (v2)        if FIND-SET(u) !== FIND-SET(v)           //then push that edge into A           A.push((u, v))          // & merge the sets of u & v into one set          Union(u, v) return A

The time complexity of this algorithm is O(E log E) or O(V log E), where E is the number of edges and V is the number of vertices.

Prim’s Algorithms

Prim’s algorithm is a greedy algorithm used to find the minimum spanning tree of an undirected graph from an arbitrary vertex of the graph.

Steps:

Track all the vertices with minimum edge weights, parents of each vertex, and the root r node.
Initialize all the key values of the vertices to infinity, except the root value.
Traverse through each unvisited adjacent vertex v of the previously visited vertex, if the weight of each edge (u, v) is less than the current key value of the vertex v , update v as edge (u, v) weight w.

Pseudocode

MST-PRIM ( G, w,  r)   // for each vertex in the graph, we give 2 attributes
   forEach u ∈ G.V      // initialize each u to infinity
      key[u] = ∞      // a parent; each parent initialized to null
      parent[u] = null      // next, select a root and set it to 0, because a root doesn't have a parent
      key[r] = 0      // next, create Q which holds all the vertices in the graph
      Q = V   // while Q is not empty
   while (Q !== null)      // find the vertex in the queue with the smallest key, & add it to the set A
      u = EXTRACT-MIN(Q)                              //O( V log V)      // update all the vertices that’s adj to the vertex v
      for each v ∈ G.Adj[u]                                               // as long as the weight of the key is less than the       weight of the edge(2 < infinity)
          if v ∈ Q and (w, u) < v.key            // update the parent and the key
            v.pi = u
            v.key = w(u, v)

The run time of this algorithm is O(V log V + E log V) = O(E log V), E is the number of edges and V is the number of vertices. Prim’s algorithms can be improved using Fibonacci heaps, which leads to O(E + log V) run time.

Type Checking using PropTypes in React

12 Most Common JavaScript Number Methods

12 Must KnowArray Methods for the Next Interview — JavaScript

Arrays: Left Rotation (JavaScript)

How to deploy Rails App on Heroku?

fetch() API in JS

How to Make Your LinkedIn Profile Stand Out & Get Better Opportunities in 2020?

How to Create Simple Forms in React?

How To Solve Loop Detection Interview Question? | Crack The Coding Interview (6th edition)

Markdown — A Easier & Fast to Learn Markup Language

Data Structure — Linked List| SINGLY LINKED LIST PRACTICE(LeetCode)

Debug JS Code with DevTool Network Tab