Finding Minimal Spanning Trees using Kruskal’s Algorithm in MFC / C++ / Boost libraries

Kruskal’s algorithm is used to find the minimal spanning tree for a network with a set of weighted links. This might be a telecoms network, or the layout for planning pipes and cables, or one of many other applications.

It is a greedy algorithm that finds the set of links for which the total weight is a minimum, subject to the constraint that the resulting network is a tree containing no cycles. In other words, the objective is to produce a spanning tree of minimal weight.

In this implementation, the Boost Graph Library is used to take an undirected graph represented by a node or edge list, along with the weights of each link in the graph, and return the edge list that comprises the minimal spanning tree. 

If it is just a simple C++ implementation of Kruskal’s algorithm you are after, without GUI and Boost libraries, here is another post with some downloadable code.

The example implementation that I used in my own version is given below:

#include "stdafx.h"
#include "Algorithm.h"

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/kruskal_min_spanning_tree.hpp>

using namespace boost;
using namespace std;

//
// Kruskal's algorithm for finding minimum spanning tree
//
void Algorithm::Kruskal( Network &network, vector< Link > &mst )
{
    typedef adjacency_list < vecS,
                             vecS,
                             undirectedS,
                             no_property,
                             property < edge_weight_t, int >> Graph;

     typedef graph_traits < Graph >::edge_descriptor   Edge;
     typedef graph_traits < Graph >::vertex_descriptor Vertex;
     typedef std::pair<int, int> E;

     const int num_nodes = network.GetNodeCount();
     const int num_links = network.GetLinkCount();   

     Graph g( num_nodes );

     property_map< Graph, edge_weight_t >::type weightmap = get( edge_weight, g );

     for ( size_t j = 0;
           j < num_links;
           ++j )
     {
         Edge e;
         bool inserted;
         tie( e, inserted ) = add_edge( network.GetLinkStartNode( j ),
                                        network.GetLinkEndNode( j ),
                                        g );

         weightmap[ e ] = (size_t) network.GetLinkWeight( j );
     }

     property_map < Graph, edge_weight_t >::type weight =
         get( edge_weight, g );

     std::vector< Edge > spanning_tree;

     kruskal_minimum_spanning_tree( g, std::back_inserter( spanning_tree ) );

     std::cout << "Print the edges in the MST:" << std::endl;

     for ( vector::iterator ei = spanning_tree.begin();
           ei != spanning_tree.end();
           ++ei )
     {
         Link l( (int) source(*ei, g),
                 (int) target(*ei, g),
                 (int) weight[*ei] );

         mst.push_back( l );
     }
}

This implementation also provides a graphical representation of the nodes and their interconnecting links using standard MFC calls to draw the network links and nodes. Nodes are added by a left mouse click and their integer identifiers are allocated in ascending numerical order

To allocate a link, left-click near the vicinity of the intended ‘start’ node, hold the mouse button down and drag towards the intended ‘end’ node before releasing:

Set the ‘weights’ of the interconnecting links by right-clicking the link and choosing ‘Link Properties’ from the drop-down menu. The default value for each link added is 1.0 units. The user also has the option to delete selected links via the same drop-down menu: