Given an undirected, connected and weighted graph, find Minimum Spanning Tree (MST) of the graph using Kruskal’s algorithm.

Kruskal’s Minimum Spanning Tree using STL in C++

Input :   Graph as an array of edges
Output :  Edges of MST are 
          6 - 7
          2 - 8
          5 - 6
          0 - 1
          2 - 5
          2 - 3
          0 - 7
          3 - 4
          
          Weight of MST is 37

Note :  There are two possible MSTs, the other
        MST includes edge 1-2 in place of 0-7.

We have discussed below Kruskal’s MST implementations.

Greedy Algorithms | Set 2 (Kruskal’s Minimum Spanning Tree Algorithm)

Below are the steps for finding MST using Kruskal’s algorithm

  1. Sort all the edges in non-decreasing order of their weight.
  2. Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If cycle is not formed, include this edge. Else, discard it.
  3. Repeat step#2 until there are (V-1) edges in the spanning tree.

Here are some key points which will be useful for us in implementing the Kruskal’s algorithm using STL.

  1. Use a vector of edges which consist of all the edges in the graph and each item of a vector will contain 3 parameters: source, destination and the cost of an edge between the source and destination.
    vector<pair<int, pair<int, int> > > edges;

    Here in the outer pair (i.e pair<int,pair<int,int> > ) the first element corresponds to the cost of a edge while the second element is itself a pair, and it contains two vertices of edge.

  2. Use the inbuilt std::sort to sort the edges in the non-decreasing order; by default the sort function sort in non-decreasing order.
  3. We use the Union Find Algorithm to check if it the current edge forms a cycle if it is added in the current MST. If yes discard it, else include it (union).

Pseudo Code:

// Initialize result
mst_weight = 0

// Create V single item sets
for each vertex v
	parent[v] = v;
	rank[v] = 0;

Sort all edges into non decreasing 
order by weight w

for each (u, v) taken from the sorted list  E
    do if FIND-SET(u) != FIND-SET(v)
        print edge(u, v)
        mst_weight += weight of edge(u, v)
        UNION(u, v)

Below is C++ implementation of above algorithm.

[pastacode lang=”cpp” manual=”%2F%2F%20C%2B%2B%20program%20for%20Kruskal’s%20algorithm%20to%20find%20Minimum%0A%2F%2F%20Spanning%20Tree%20of%20a%20given%20connected%2C%20undirected%20and%0A%2F%2F%20weighted%20graph%0A%23include%3Cbits%2Fstdc%2B%2B.h%3E%0Ausing%20namespace%20std%3B%0A%20%0A%2F%2F%20Creating%20shortcut%20for%20an%20integer%20pair%0Atypedef%20%20pair%3Cint%2C%20int%3E%20iPair%3B%0A%20%0A%2F%2F%20Structure%20to%20represent%20a%20graph%0Astruct%20Graph%0A%7B%0A%20%20%20%20int%20V%2C%20E%3B%0A%20%20%20%20vector%3C%20pair%3Cint%2C%20iPair%3E%20%3E%20edges%3B%0A%20%0A%20%20%20%20%2F%2F%20Constructor%0A%20%20%20%20Graph(int%20V%2C%20int%20E)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20this-%3EV%20%3D%20V%3B%0A%20%20%20%20%20%20%20%20this-%3EE%20%3D%20E%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Utility%20function%20to%20add%20an%20edge%0A%20%20%20%20void%20addEdge(int%20u%2C%20int%20v%2C%20int%20w)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20edges.push_back(%7Bw%2C%20%7Bu%2C%20v%7D%7D)%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Function%20to%20find%20MST%20using%20Kruskal’s%0A%20%20%20%20%2F%2F%20MST%20algorithm%0A%20%20%20%20int%20kruskalMST()%3B%0A%7D%3B%0A%20%0A%2F%2F%20To%20represent%20Disjoint%20Sets%0Astruct%20DisjointSets%0A%7B%0A%20%20%20%20int%20*parent%2C%20*rnk%3B%0A%20%20%20%20int%20n%3B%0A%20%0A%20%20%20%20%2F%2F%20Constructor.%0A%20%20%20%20DisjointSets(int%20n)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Allocate%20memory%0A%20%20%20%20%20%20%20%20this-%3En%20%3D%20n%3B%0A%20%20%20%20%20%20%20%20parent%20%3D%20new%20int%5Bn%2B1%5D%3B%0A%20%20%20%20%20%20%20%20rnk%20%3D%20new%20int%5Bn%2B1%5D%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Initially%2C%20all%20vertices%20are%20in%0A%20%20%20%20%20%20%20%20%2F%2F%20different%20sets%20and%20have%20rank%200.%0A%20%20%20%20%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%3D%20n%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20rnk%5Bi%5D%20%3D%200%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2Fevery%20element%20is%20parent%20of%20itself%0A%20%20%20%20%20%20%20%20%20%20%20%20parent%5Bi%5D%20%3D%20i%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Find%20the%20parent%20of%20a%20node%20’u’%0A%20%20%20%20%2F%2F%20Path%20Compression%0A%20%20%20%20int%20find(int%20u)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F*%20Make%20the%20parent%20of%20the%20nodes%20in%20the%20path%0A%20%20%20%20%20%20%20%20%20%20%20from%20u–%3E%20parent%5Bu%5D%20point%20to%20parent%5Bu%5D%20*%2F%0A%20%20%20%20%20%20%20%20if%20(u%20!%3D%20parent%5Bu%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20parent%5Bu%5D%20%3D%20find(parent%5Bu%5D)%3B%0A%20%20%20%20%20%20%20%20return%20parent%5Bu%5D%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Union%20by%20rank%0A%20%20%20%20void%20merge(int%20x%2C%20int%20y)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20x%20%3D%20find(x)%2C%20y%20%3D%20find(y)%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20Make%20tree%20with%20smaller%20height%0A%20%20%20%20%20%20%20%20%20%20%20a%20subtree%20of%20the%20other%20tree%20%20*%2F%0A%20%20%20%20%20%20%20%20if%20(rnk%5Bx%5D%20%3E%20rnk%5By%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20parent%5By%5D%20%3D%20x%3B%0A%20%20%20%20%20%20%20%20else%20%2F%2F%20If%20rnk%5Bx%5D%20%3C%3D%20rnk%5By%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20parent%5Bx%5D%20%3D%20y%3B%0A%20%0A%20%20%20%20%20%20%20%20if%20(rnk%5Bx%5D%20%3D%3D%20rnk%5By%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20rnk%5By%5D%2B%2B%3B%0A%20%20%20%20%7D%0A%7D%3B%0A%20%0A%20%2F*%20Functions%20returns%20weight%20of%20the%20MST*%2F%0A%20%0Aint%20Graph%3A%3AkruskalMST()%0A%7B%0A%20%20%20%20int%20mst_wt%20%3D%200%3B%20%2F%2F%20Initialize%20result%0A%20%0A%20%20%20%20%2F%2F%20Sort%20edges%20in%20increasing%20order%20on%20basis%20of%20cost%0A%20%20%20%20sort(edges.begin()%2C%20edges.end())%3B%0A%20%0A%20%20%20%20%2F%2F%20Create%20disjoint%20sets%0A%20%20%20%20DisjointSets%20ds(V)%3B%0A%20%0A%20%20%20%20%2F%2F%20Iterate%20through%20all%20sorted%20edges%0A%20%20%20%20vector%3C%20pair%3Cint%2C%20iPair%3E%20%3E%3A%3Aiterator%20it%3B%0A%20%20%20%20for%20(it%3Dedges.begin()%3B%20it!%3Dedges.end()%3B%20it%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20int%20u%20%3D%20it-%3Esecond.first%3B%0A%20%20%20%20%20%20%20%20int%20v%20%3D%20it-%3Esecond.second%3B%0A%20%0A%20%20%20%20%20%20%20%20int%20set_u%20%3D%20ds.find(u)%3B%0A%20%20%20%20%20%20%20%20int%20set_v%20%3D%20ds.find(v)%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Check%20if%20the%20selected%20edge%20is%20creating%0A%20%20%20%20%20%20%20%20%2F%2F%20a%20cycle%20or%20not%20(Cycle%20is%20created%20if%20u%0A%20%20%20%20%20%20%20%20%2F%2F%20and%20v%20belong%20to%20same%20set)%0A%20%20%20%20%20%20%20%20if%20(set_u%20!%3D%20set_v)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Current%20edge%20will%20be%20in%20the%20MST%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20so%20print%20it%0A%20%20%20%20%20%20%20%20%20%20%20%20cout%20%3C%3C%20u%20%3C%3C%20%22%20-%20%22%20%3C%3C%20v%20%3C%3C%20endl%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Update%20MST%20weight%0A%20%20%20%20%20%20%20%20%20%20%20%20mst_wt%20%2B%3D%20it-%3Efirst%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Merge%20two%20sets%0A%20%20%20%20%20%20%20%20%20%20%20%20ds.merge(set_u%2C%20set_v)%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20return%20mst_wt%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20functions%0Aint%20main()%0A%7B%0A%20%20%20%20%2F*%20Let%20us%20create%20above%20shown%20weighted%0A%20%20%20%20%20%20%20and%20unidrected%20graph%20*%2F%0A%20%20%20%20int%20V%20%3D%209%2C%20E%20%3D%2014%3B%0A%20%20%20%20Graph%20g(V%2C%20E)%3B%0A%20%0A%20%20%20%20%2F%2F%20%20making%20above%20shown%20graph%0A%20%20%20%20g.addEdge(0%2C%201%2C%204)%3B%0A%20%20%20%20g.addEdge(0%2C%207%2C%208)%3B%0A%20%20%20%20g.addEdge(1%2C%202%2C%208)%3B%0A%20%20%20%20g.addEdge(1%2C%207%2C%2011)%3B%0A%20%20%20%20g.addEdge(2%2C%203%2C%207)%3B%0A%20%20%20%20g.addEdge(2%2C%208%2C%202)%3B%0A%20%20%20%20g.addEdge(2%2C%205%2C%204)%3B%0A%20%20%20%20g.addEdge(3%2C%204%2C%209)%3B%0A%20%20%20%20g.addEdge(3%2C%205%2C%2014)%3B%0A%20%20%20%20g.addEdge(4%2C%205%2C%2010)%3B%0A%20%20%20%20g.addEdge(5%2C%206%2C%202)%3B%0A%20%20%20%20g.addEdge(6%2C%207%2C%201)%3B%0A%20%20%20%20g.addEdge(6%2C%208%2C%206)%3B%0A%20%20%20%20g.addEdge(7%2C%208%2C%207)%3B%0A%20%0A%20%20%20%20cout%20%3C%3C%20%22Edges%20of%20MST%20are%20%5Cn%22%3B%0A%20%20%20%20int%20mst_wt%20%3D%20g.kruskalMST()%3B%0A%20%0A%20%20%20%20cout%20%3C%3C%20%22%5CnWeight%20of%20MST%20is%20%22%20%3C%3C%20mst_wt%3B%0A%20%0A%20%20%20%20return%200%3B%0A%7D” message=”” highlight=”” provider=”manual”/]

Output :

Edges of MST are 
          6 - 7
          2 - 8
          5 - 6
          0 - 1
          2 - 5
          2 - 3
          0 - 7
          3 - 4
          
          Weight of MST is 37