Kruskal's Algorithm | Minimum Spanning Tree


When edges connects all vertices in a graph and form a tree then it is known as spanning tree. While connecting edges no cycle should be formed. A minimum spanning tree is the spanning tree whose sum of edge weights is as small as possible.

Initially no vertices are connected to any other vertex means the spanning tree does not contain any edges, it only contain vertices. Kruskal’s algorithm adds an edge to the tree which has the smallest weight if it does not create a cycle.

Kruskal’s algorithm is a greedy algorithm, because at each step it adds an edge with minimum possible weight.

Here are the given edges and their weight, arranged in increasing order.

Kruskal

kruskal

In the above fig. algorithm add edges with minimum weight and if it does not create cycle. Weight of edge b - e is less than edge d – f but it was creating a cycle a – b – e – a , so it was not added.

Implementation

In fig. (c) there are two disjoint sets. First set contains {a, b} and representative of this set is a whereas second set contains {e, f} and representative of this set is e. Thus a and b forms a tree and e and f forms another tree. All vertices in a tree have same representative (or parent).

1
2
3
4
5
6
7
8
9
10

std::size_t find_set(std::size_t vertex)
{
    auto it = vertices[vertex].parent;
    std::size_t parent_id = it->id;
    if (it != &vertices[vertex])
    {
        parent_id = find_set(it->id);
    }
    return parent_id;
}

find_set tells us about the representative of the vertex. find_set(a) = find_set(b) and find_set(a) ≠ find_set(b).

1
2
3
4
5

void make_set(std::size_t vertex)
{
    vertices[vertex].parent = &vertices[vertex];
    vertices[vertex].rank   = 0;
}

make_set is the first function algorithm calls. Initially, number of disjoint sets is equal to the number of vertices, since there is no spanning tree and no vertices are connected like in fig. (a). It sets rank of each vertex to 0 and make them representative of their set since there is only one element in the set, which is the vertex.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

void link(std::size_t to, std::size_t from)
{
    if (vertices[to].rank > vertices[from].rank)
    {
        vertices[from].parent = &vertices[to];
    }
    else
    {
        vertices[to].parent = &vertices[from];
        if (vertices[to].rank == vertices[from].rank)
        {
            vertices[from].rank = vertices[from].rank + 1;
        }
    }
}

to is the vertex which is already in a spanning tree and from is the vertex which is being added to the tree.

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

void union_(std::size_t ver1, std::size_t ver2)
{
    link( find_set(vertices[ver1].id), find_set(vertices[ver2].id) );
}

void kruskal()
{
    for (std::size_t i = 0; i < vertices.size(); i++)
    {
        make_set(i);
    }
    //sort according to weight in increasing order
    std::sort(edge_weight.begin(), edge_weight.end(),
              [](const auto& left, const auto& right)
              { return left.second < right.second; } );

    for (auto& e: edge_weight)
    {
        if ( find_set(vertices[e.first.first].id)
            != find_set(vertices[e.first.second].id) )
           {
                processed.insert(e.first.first);
                processed.insert(e.first.second);
                cost = cost + e.second;
                union_(e.first.first, e.first.second);
           }
    }
    std::cout << "The total cost is : " << cost << "\n";
}

After function make_set is called, the edges are sorted in increasing order according to their weight. Edges are added only if they are not in the same set means only if they do not have same parent. In fig. (e) edge-weight of b – e is smaller than that of d - f but since b and e belongs to same set and if it is added a cycle will create in the graph.

Here is the C++ implementation of Kruskal's Algorithm

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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166

#include <iostream>
#include <vector>
#include <map>
#include <unordered_set>
#include <algorithm>

class Graph
{
    std::size_t cost = 0;
    struct Vertex
    {
        std::size_t id;
        Vertex * parent = nullptr;
        std::size_t rank;
        Vertex(std::size_t id) : id(id) {}
    };

    using edges = std::pair<std::size_t, std::size_t>;

    std::vector<Vertex> vertices = {};
    std::vector< std::pair<edges, std::size_t> > edge_weight;
    std::unordered_set<std::size_t> processed = {};

  public:
    Graph(std::size_t);
    void add_edge(std::size_t, std::size_t, int);
    void kruskal();

  private:
    void make_set(std::size_t);
    void link(std::size_t, std::size_t);
    void union_(std::size_t, std::size_t);
    std::size_t find_set(std::size_t);
};

Graph::Graph(std::size_t size)
{
    vertices.reserve(size);
    for (int i = 0; i < size; i++)
    {
        vertices.emplace_back(i);
    }
}

std::size_t Graph::find_set(std::size_t vertex)
{
    auto it = vertices[vertex].parent;
    std::size_t parent_id = it->id;
    if (it != &vertices[vertex])
    {
        parent_id = find_set(it->id);
    }
    return parent_id;
}

void Graph::make_set(std::size_t vertex)
{
    vertices[vertex].parent = &vertices[vertex];
    vertices[vertex].rank   = 0;
}

void Graph::link(std::size_t to, std::size_t from)
{
    if (vertices[to].rank > vertices[from].rank)
    {
        vertices[from].parent = &vertices[to];
    }
    else
    {
        vertices[to].parent = &vertices[from];
        if (vertices[to].rank == vertices[from].rank)
        {
            vertices[from].rank = vertices[from].rank + 1;
        }
    }
}

void Graph::union_(std::size_t ver1, std::size_t ver2)
{
    link( find_set(vertices[ver1].id),
          find_set(vertices[ver2].id) );
}

void Graph::add_edge(std::size_t src, std::size_t dest, int weight)
{
    if (src == dest)
    {
        throw std::logic_error("src == dest");
    }

    if (src < 0 || vertices.size() <= src)
    {
        throw std::out_of_range("src");
    }

    if (dest < 0 || vertices.size() <= dest)
    {
        throw std::out_of_range("dest");
    }


    int flag = 0;
    for (auto& it: edge_weight)
    {
        if (it.first.first == src && it.first.second == dest)
        {
            flag = 1;
            break;
        }
    }
    if (flag == 0)
    {
        //insert vertices with their associated weight
        edge_weight.push_back({ {src, dest}, weight});
    }
    else
    {
        throw std::logic_error("existing edge");
    }
}

void Graph::kruskal()
{
    for (std::size_t i = 0; i < vertices.size(); i++)
    {
        make_set(i);
    }
    //sort according to weight in increasing order
    std::sort(edge_weight.begin(), edge_weight.end(),
              [](const auto& left, const auto& right)
              { return left.second < right.second; } );

    for (auto& e: edge_weight)
    {
        if ( find_set(vertices[e.first.first].id)
            != find_set(vertices[e.first.second].id) )
           {
                processed.insert(e.first.first);
                processed.insert(e.first.second);
                cost = cost + e.second;
                union_(e.first.first, e.first.second);
           }
    }
    std::cout << "The total cost is : " << cost << "\n";
}

int main()
{
    Graph grp(9);
    grp.add_edge(0, 1, 4);
    grp.add_edge(0, 2, 8);
    grp.add_edge(1, 2, 11);
    grp.add_edge(1, 3, 8);
    grp.add_edge(3, 4, 2);
    grp.add_edge(4, 2, 7);
    grp.add_edge(2, 5, 1);
    grp.add_edge(5, 4, 6);
    grp.add_edge(3, 6, 7);
    grp.add_edge(3, 8, 4);
    grp.add_edge(5, 8, 2);
    grp.add_edge(6, 7, 9);
    grp.add_edge(6, 8, 14);
    grp.add_edge(7, 8, 10);

    grp.kruskal();
}

Compile with command g++ -std=c++14 kruskal.cpp -o kruskal

View this code on Github.

Get this post in pdf - Kruskal’s Algorithm

Reference:
Introduction to Algorithms
The Algorithm Design Manual
Data Structures and Algorithms Made Easy
Competitive Programmer’s Handbook - Antti Laaksonen

You may also like

Dijkstra’s Algorithm
Bellman Ford Algorithm
Breadth First Search using Adjacency List
Depth First Search using Adjacency List