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):
    ds.makeSet(i)
for edge in edges:
    startVertex,endVertex = edge[0]
    if ds.findParent(ds.setS[startVertex])==ds.findParent(ds.setS[endVertex]):
        pass
    else:
        ds.unionSet(startVertex,endVertex)
        finalEdges.append(edge)
        if len(finalEdges)==n-1:
            break

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

kmst1
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)

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

KMST3.png
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

KMST4.png
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

Advertisements

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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