Home
Kruskal’s Algorithm in C++

Kruskal’s Algorithm in C++

25 July 2012 C++ / MFC / STL 6 Comments

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
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:

Kruskal

C++ source code downloadable from here.

Related Posts

About The Author

Andy