Kruskal’s Algorithm for finding Minimum Spanning Tree

Given a undirected, connected and weighted graph, construct a minimum spanning tree out of it using Kruskal’s Algorithm.

 
A Minimum Spanning Tree is a spanning tree of a connected, undirected graph. It connects all the vertices together with the minimal total weighting for its edges.

  kruskal-1

For example, consider above graph. Its minimum spanning tree will be below tree with exactly N-1 edges where N is number of vertices in the graph and sum of weights of edges is as minimum as possible.
Kruskal’s Algorithm

 


 

Prerequisite: Union-Find Algorithm for Cycle Detection in undirected graph

 
We can use Kruskal’s Minimum Spanning Tree algorithm which is a greedy algorithm to find a minimum spanning tree for a connected weighted graph. Kruskal’s Algorithm works by finding a subset of the edges from the given graph covering every vertex present in the graph such that they forms a tree (called MST) and sum of weights of edges is as minimum as possible.

Let G = (V, E) be the given graph. Initially our MST contains only vertices of given graph with no edges. In other words, initially MST has V connected components with each vertex acting as one connected component. The goal is to add minimum weight edges to our MST such that we are left with single connected component that comprises all the vertices of graph. Below is the complete algorithm –


Sort all edges in the graph G in the order of their increasing weights;
repeat V-1 times    // as MST contains V-1 edges
{
    Select the next edge with minimum weight from the graph G;

    if (no cycle is formed by adding the edge in MST i.e. the edge connects two
            different connected components in MST)
        add the edge to MST;
}

Let’s illustrate this by taking example of above graph. Initially our MST consists of only the vertices of given graph with no edges. We start by considering smallest weighted edge 0-3 having weight 5. As no cycle is formed, we include it in our MST.

  kruskal-2

We next consider smallest weighted edge 2-4 also having weight 5. As no cycle is formed, we include it in our MST.

  kruskal-3

We next consider smallest weighted edge 3-5 having weight 6. As no cycle is formed, we include it in our MST.

  kruskal-4

We next consider smallest weighted edge 0-1 having weight 7. As no cycle is formed, we include it in our MST.

  kruskal-5

We next consider smallest weighted edge 1-4 also having weight 7. As no cycle is formed, we include it in our MST.

  kruskal-6

We next consider smallest weighted edge 5-4 having weight 8. But including this edge in MST will result in a cycle 0-1-4-5-3-0, so we discard it.

  kruskal-7

We next consider smallest weighted edge 1-2 also having weight 8. But including this edge in MST will result in a cycle 1-2-4-1, so we discard it.

  kruskal-8

We next consider smallest weighted edge 3-1 also having weight 9. But including this edge in MST will result in a cycle 0-1-3-0, so we discard it.

  kruskal-9

Finally we consider next smallest weighted edge 4-6 also having weight 9. As no cycle is formed, we include it in our MST.
  kruskal-10

MST is now connected (contaning V-1 edges). So we discard all remaining edges.

  kruskal-11

Below is the pseudocode of Kruskal’s Algorithm as per wikipedia. It uses disjoint-set data structure.

KRUSKAL(graph G)

MST = {}

for each vertex v belonging G.V:
    MAKE-SET(v)
    
for each (u, v) in G.E ordered by weight(u, v), increasing:
    if FIND-SET(u) != FIND-SET(v):
        add {(u, v)} to set MST
        UNION(u, v)

return MST

Please note that if the graph is not connected, then Kruskal’s Algorithm finds a Minimum Spanning Forest which is a minimum spanning tree for each connected component of the graph.

C++

Download   Run Code

Output:

(2, 4, 5)
(0, 3, 5)
(3, 5, 6)
(1, 4, 7)
(0, 1, 7)
(4, 6, 9)

References:

1. https://en.wikipedia.org/wiki/Kruskal%27s_algorithm

2. http://lcm.csa.iisc.ernet.in/dsa/node184.html

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz