Minimum Spanning Tree

Kruskal’s Algorithm

Hey, this blog, I will be going to explain a small part or you can say a subsection of Spanning Tree i.e Kruskal’s Algorithm, a greedy algorithm similarly like Boruvka and Prims.

You make this journey more interesting, I have used examples and pictures to make this more facile and intuitive.

I know you all will be as excited as I am, so let’s start our journey.

Before we jump directly to Kruskal’s algorithm, let’s first understand what a graph is.

What is a Graph?

Interconnected Nodes in a graph

A graph is made up of a finite number of vertices (or nodes) and a set of Edges that connect them.

Let G be a graph.The following four conditions are satisfied:

  1. G be a tree.
  2. Any two vertices of G are connected by a unique path.
  3. G is connected and any edge of G is a bridge.

What is a Minimum Spanning Tree?

In this section, we consider spanning forests in networks. Thus let (G,w) be a network. For any subset T of the edge set of G, we define the weight of T by an expression: w (T) = ∑w(e) where e belongs to T.

A spanning Tree forest of G is called a minimal spanning forest if its weight is minimal among all the weights of spanning forests, a minimal spanning tree has a minimal weight spanning tree.

But here I am not going deep, hence we restrict ourselves to spanning trees. The general case can be treated by considering a minimal spanning tree for each connected component of G. Thus, we now assume G to be connected.

Mathematical Explanation of 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

How Kruskal’s Algorithms Work?

So till now you have got an idea that its basic use is to traverse the whole tree to reach its destination i.e. to discover the subset of edges that may be used to visit all of the graph’s vertices.

Flowchart of Kruskal’s Algorithm

We start with the edges with the lowest weight in Kruskal’s method and keep adding edges until the goal is reached.

  • In the first step we will sort the whole array (parent array) in ascending order of their weights.
  • In the second step we will add the edges to the spanning tree having lowest weight, keeping a check that it should not form a cycle.
  • We will continue with this second step until we reach all vertices and a minimum spanning tree is created .

Let us try to understand with an example:

The weight of all the edges are shown below:

Now, as discussed earlier, we have to sort the weights in ascending order:

Now, according to our second point we have to construct the spanning tree.

Step 1: To begin, add the edge AB to the MST with weight 1.

Step2: Because the MST isn’t creating the cycle, add the edge DE with weight 2 to it.

Step3: Because there is no cycle or loop, add the edge BC with weight 3 to the MST.

Step4: Pick the MST’s edge CD with weight 4 because it is not generating the cycle.

Step5: After that, choose the AE edge with a weight of 5. This edge will start the cycle if it is included, therefore removes it. With a weight of 7, choose the edge AC. This edge will start the cycle if it is included, therefore removes it. With a weight of 10, choose the edge AD. This edge will start the cycle if it is included, therefore removes it.

The cost of the MST is = AB + DE + BC + CD = 1 + 2 + 3 + 4 = 10.

--

--

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