# 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;

public:
DenseGRAPH(int V, bool digraph = false) :
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;
}

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

Ecnt--;

}

EdgePtr edge(int v, int w) const

// Get the weighted edges
void edges( std::vector<EdgePtr>& edges )
{
for( int u = 0; u < V(); ++u )
{

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

};

template <class Edge>
{
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 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: