Kruskal’s Algorithm in C++

A simple C++ implementation of Kruskal’s algorithm for finding minimal spanning trees in networks. Though I have a previous posting that accomplishes exactly the same thing, I thought that a simple implementation would be useful, one using a straightforward Graph data structure for modelling network links and nodes, does not have a graphical user interface and does not use the Boost Graph Library, which can be complicated to use and not to everyone’s preference.

Pseudocode

KRUSKAL(G):
A = ∅
foreach v ∈ G.V:
MAKE-SET(v)
foreach (u, v) ordered by weight(u, v), increasing:
if FIND-SET(u) ≠ FIND-SET(v):
A = A ∪ {(u, v)}
UNION(u, v)
return A

The Graph data structure

The Graph data structure is described in more detail in a previous post under the section titled “An alternative Graph class”. Suffice to say it provides us with a means of inserting and deleting network links so as to capture a network topology. Class outline as follows:

#include <vector>
#include <algorithm>

// This code is from "Algorithms in C++, Third Edition,"
// by Robert Sedgewick, Addison-Wesley, 2002.
class Edge 
{
public:
    int v, w;
    double wt;
    Edge(int v = -1, int w = -1, double wt = 0.0) : 
        v(v), w(w), wt(wt) { }
};

typedef std::shared_ptr<Edge> EdgePtr;

struct EdgeSort
{
	bool operator() ( const EdgePtr& ep1, const EdgePtr& ep2  )
	{
		return ep1->wt < ep2->wt;
	}
};

template <class Edge>
class DenseGRAPH
{ 
private:
    int Vcnt, Ecnt;
    bool digraph;
    std::vector <std::vector<EdgePtr>> adj;

public:
    DenseGRAPH(int V, bool digraph = false) :
        adj(V), 
        Vcnt(V), 
        Ecnt(0), 
        digraph(digraph)
    { 
        for ( int i = 0; i < V; i++ ) adj[i].resize( V );
    }

    int V() const { return Vcnt; }
    int E() const { return Ecnt; }

    bool directed() const { return digraph; }
    
    void insert( EdgePtr e )
    { 
        int v = e->v;
        int w = e->w;
        if (adj[v][w] == 0) Ecnt++;
        adj[v][w] = e;
        if (!digraph) adj[w][v] = e;
    } 

    void remove(EdgePtr e)
    { 
        int v = e->v;
        int w = e->w;

        if (adj[v][w] != 0)  
            Ecnt--;

        adj[v][w] = 0;

        if (!digraph) adj[w][v] = 0; 
    } 

    EdgePtr edge(int v, int w) const 
    { return adj[v][w]; }

	// Get the weighted edges
	void edges( std::vector<EdgePtr>& edges )
	{
		for( int u = 0; u < V(); ++u )
		{
			DenseGRAPH<Edge>::adjIterator A(*this, u); 

			for ( EdgePtr e = A.beg(); !A.end(); e = A.nxt() ) 
			{ 
				if ( NULL != e )
				{
					edges.push_back( e );
				}
			}
		}
	}

    class adjIterator;
    friend class adjIterator;
};

template <class Edge>
class DenseGRAPH<Edge>::adjIterator
{ 
private:

    const DenseGRAPH &G;
    int i, v;

public:
    adjIterator(const DenseGRAPH<Edge> &G, int v) : 
        G(G), 
        v(v), 
        i(0) {}

    EdgePtr beg() { i = -1; return nxt(); }

    EdgePtr nxt()
    {
        for (i++; i < G.V(); i++)
            if (G.edge(v, i)) 
                return G.adj[v][i];
        
        return 0;
    }

    bool end() const { return i >= G.V(); }
};

Example

Consider the following 11-node network showing the network nodes and the weight values of the links connecting them:

Which is built using multiple calls to the insert API as follows:

DenseGRAPH<Edge>* graph = new DenseGRAPH<Edge>( 11, true ); 

graph->insert( EdgePtr( new Edge( 0, 1, 1.0 ) ) );    
graph->insert( EdgePtr( new Edge( 0, 2, 0.6) ) );    
graph->insert( EdgePtr( new Edge( 0, 3, 1.0 ) ) );   
graph->insert( EdgePtr( new Edge( 0, 4, 1.0 ) ) );    
graph->insert( EdgePtr( new Edge( 0, 5, 1.1 ) ) );   
graph->insert( EdgePtr( new Edge( 1, 4, 1.8 ) ) );   
graph->insert( EdgePtr( new Edge( 1, 10, 1.9 ) ) );   
graph->insert( EdgePtr( new Edge( 2, 3, 2.1 ) ) );   
graph->insert( EdgePtr( new Edge( 2, 5, 2.3) ) );   
graph->insert( EdgePtr( new Edge( 2, 6, 1.7 ) ) );   
graph->insert( EdgePtr( new Edge( 3, 4, 1.7 ) ) );  
graph->insert( EdgePtr( new Edge( 5, 6, 0.5 ) ) );  
graph->insert( EdgePtr( new Edge( 5, 7, 0.7 ) ) );  
graph->insert( EdgePtr( new Edge( 5, 8, 0.9 ) ) );  
graph->insert( EdgePtr( new Edge( 5, 9, 0.9 ) ) );  
graph->insert( EdgePtr( new Edge( 5, 10, 1.0 ) ) );     
graph->insert( EdgePtr( new Edge( 6, 7, 1.9 ) ) );  
graph->insert( EdgePtr( new Edge( 7, 8, 1.7 ) ) );  
graph->insert( EdgePtr( new Edge( 8, 9, 1.6 ) ) );  
graph->insert( EdgePtr( new Edge( 9, 10, 2.2 ) ) );  

Implementation of Kruskal algorithm

Kruskal’s algorithm works by obtaining a sorted list of the network links, and then adding each least-cost link to another set while disallowing cycles:

void KruskalMST( DenseGRAPH<Edge>* graph, std::vector<EdgePtr>& mst )
{
    const int V = graph->V();
 
    // Sort edges in non-decreasing order of their weight
	std::vector<EdgePtr> edges;
	graph->edges( edges );
	std::sort(edges.begin(), edges.end(), EdgeSort() );
 
    // Allocate memory for creating V ssubsets
	std::unique_ptr<subset[]> subsets( new subset[ V ]() );
 
    // Create V subsets with single elements
    for ( int v = 0; v < V; ++v )
    {
        subsets[v].parent = v;
        subsets[v].rank = 0;
    }
 
	for ( std::vector<EdgePtr>::iterator it = edges.begin(); it != edges.end(); ++it )
	{
		EdgePtr edgePtr = *it;

		int x = Find( subsets.get(), edgePtr->v );
		int y = Find( subsets.get(), edgePtr->w );

		// If including this edge does't cause cycle, include it
		// in result and increment the index of result for next edge
		if ( x != y )
		{
			mst.push_back( edgePtr );
			Union( subsets.get(), x, y );
		}
	}
}

Applying Kruskal then results in the following minimal spanning tree:

Console output as follows:

C++ source code downloadable from here.