Kruskal’s MST

#Day 5 

A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight.

Kruskal is one of the algorithms to find MST in a given graph. This algorithm requires knowledge of disjoint sets, which I discussed in my previous post. If you haven’t read that yet, you can head here to read.

Steps to construct this algorithm are-

  • sort the edges by their weight.
  • Create a new list (new graph) which will hold the edges.
  • Iterate over the sorted edges. check if both the vertices in the edge are in the set of disjoint sets
    • YES: check if both have the same parent(checking if the edge forms a cycle)
      • YES: discard the edge
      • NO: add the edge in the new graph and do the union of both the vertices in the disjoint set
    • NO: Add both to disjoint sets, union them and add the edge to the new graph
  • The iteration stops whenever the number of edges is equal to total vertices – 1
ds = disjointSet()
for i in xrange(1,n+1):
for edge in edges:
    startVertex,endVertex = edge[0]
    if ds.findParent(ds.setS[startVertex])==ds.findParent(ds.setS[endVertex]):
        if len(finalEdges)==n-1:

For example, We have the following graph to work on –

Image: 1

Now we sort all the edges and get

start      end       weight

1                3             3

3               2             4

1                2             5

3               4             5

4              1              6

2             4              7

We start iterating over the edges and choose edge between 1 and 3 of weight 3.

Both are not in the same subset (not forming a cycle so we add them to our new graph)

Image: 2

After this, we choose 3-2 with weight 4 . This also doesn’t form a cycle so we add this too to our new graph.

Image: 3

Now we take  1-2 with weight 5 But this contains a cycle. So we don’t add this to our new graph and move on to next edge.

Then we have 3-4 with weight 5, which doesn’t form a cycle so we add this to the graph. The number of edges in the new graph becomes 3 which is equal to the number of vertices-1.

e= v-1 hence the algorithm stops here and we got the final new MST as Image: 4

Image: 4

As a final result, we have an MST with weight 12.

Time Complexity

The time complexity of this algorithm is O(ELog(E) + E).

Sorting the edges takes O(ELOG(E)),  E is the number of edges. Adding those to vertices in the graph takes O(E) time.

Source Code

Source code implementation of this algorithm in python can be found here. Source code link

Hackerrank Implementation

If you want to implement this algorithm, you can solve this problem on Hackerrank with few minor change in the iteration. Problem Link

If you still want a peek on the solution of the same look here


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s