mafulechka
mafulechkaJuly 25, 2019, 2 p.m.

Kruskal's algorithm

Kruskal's algorithm is a minimum spanning tree algorithm that takes a graph as input and finds a subset of that graph's edges that forms a tree that includes each vertex and also has the minimum sum of weights among all trees that can be formed from a graph.


How the Kruskal algorithm works

It falls under a class of algorithms called "greedy" algorithms that find a local optimum in the hope of finding a global optimum.

We start with the edges with the lowest weight and keep adding edges until we reach our goal.

The steps to implement Kruskal's algorithm are as follows:

  1. Sort all edges from low weight to high weight.
  2. Take the edge with the smallest weight and add it to the spanning tree. If adding an edge created a cycle, then reject that edge.
  3. Keep adding edges until you reach all the vertices.

Kruskal algorithm example

Kruskal's algorithm. Pseudocode.

Any minimum spanning tree algorithm revolves around checking whether an edge creates a cycle or not.

The most common way to figure this out is with the Union FInd algorithm . The Union-Find algorithm divides the vertices into clusters and allows us to check if two vertices belong to the same cluster or not, and therefore decide whether adding an edge creates a cycle.

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

Implementation of Kruskal's algorithm in C++

Following is the code for implementation in C++. We use standard template libraries to make our work easier and cleaner.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define edge pair<int,int>

class Graph {
private:
    vector<pair<int, edge>> G; // graph
    vector<pair<int, edge>> T; // mst
    int *parent;
    int V; // number of vertices/nodes in graph
public:
    Graph(int V);
    void AddWeightedEdge(int u, int v, int w);
    int find_set(int i);
    void union_set(int u, int v);
    void kruskal();
    void print();
};
Graph::Graph(int V) {
    parent = new int[V];

    //i 0 1 2 3 4 5
    //parent[i] 0 1 2 3 4 5
    for (int i = 0; i < V; i++)
        parent[i] = i;

    G.clear();
    T.clear();
}
void Graph::AddWeightedEdge(int u, int v, int w) {
    G.push_back(make_pair(w, edge(u, v)));
}
int Graph::find_set(int i) {
    // If i is the parent of itself
    if (i == parent[i])
        return i;
    else
        // Else if i is not the parent of itself
        // Then i is not the representative of his set,
        // so we recursively call Find on its parent
        return find_set(parent[i]);
}

void Graph::union_set(int u, int v) {
    parent[u] = parent[v];
}
void Graph::kruskal() {
    int i, uRep, vRep;
    sort(G.begin(), G.end()); // increasing weight
    for (i = 0; i < G.size(); i++) {
        uRep = find_set(G[i].second.first);
        vRep = find_set(G[i].second.second);
        if (uRep != vRep) {
            T.push_back(G[i]); // add to tree
            union_set(uRep, vRep);
        }
    }
}
void Graph::print() {
    cout << "Edge :" << " Weight" << endl;
    for (int i = 0; i < T.size(); i++) {
        cout << T[i].second.first << " - " << T[i].second.second << " : "
                << T[i].first;
        cout << endl;
    }
}
int main() {
    Graph g(6);
    g.AddWeightedEdge(0, 1, 4);
    g.AddWeightedEdge(0, 2, 4);
    g.AddWeightedEdge(1, 2, 2);
    g.AddWeightedEdge(1, 0, 4);
    g.AddWeightedEdge(2, 0, 4);
    g.AddWeightedEdge(2, 1, 2);
    g.AddWeightedEdge(2, 3, 3);
    g.AddWeightedEdge(2, 5, 2);
    g.AddWeightedEdge(2, 4, 4);
    g.AddWeightedEdge(3, 2, 3);
    g.AddWeightedEdge(3, 4, 3);
    g.AddWeightedEdge(4, 2, 4);
    g.AddWeightedEdge(4, 3, 3);
    g.AddWeightedEdge(5, 2, 2);
    g.AddWeightedEdge(5, 4, 3);
    g.kruskal();
    g.print();
    return 0;
}

When we run the program, we get output like:

Edge : Weight
1 - 2 : 2
2 - 5 : 2
2 - 3 : 3
3 - 4 : 3
0 - 1 : 4

Kruskal's algorithm vs Prima

Prim's algorithm is another popular minimum spanning tree algorithm that uses a different logic to find the MST graph. Instead of starting at an edge, Prim's algorithm starts at a vertex and keeps adding the least weighted edges that are not in the tree until all vertices are covered.

We recommend hosting TIMEWEB
We recommend hosting TIMEWEB
Stable hosting, on which the social network EVILEG is located. For projects on Django we recommend VDS hosting.

Do you like it? Share on social networks!

Vladimir Sergeevich
  • July 25, 2019, 4:20 p.m.
  • (edited)

Я так понимаю, это перевод статьи?

Вот такие фразы выглядят стремно: "Любой минимальный алгоритм остовного дерева"
"популярным алгоритмом минимального остовного дерева"
Возможно, должно быть "алгоритмом построения ..."

Первое предложение тоже несогласованное.

Странной кажется идея запихивания графа в класс. Да и все равно можно выстрелить в ногу, вызвав print до вызова kruskal.

Не очевидна связь приведенного кода с описанным алгоритмом. - Что это за массив parent и почему (кстати) он не уничтожается в деструкторе?

Псевдокод не понятный. Что делает функция UNION(u, v) ?
Обе строки 7 и 8 вложены внутрь блока if?

У нормальной реализации алгоритма сложность N*log(N). А у вас для каждого узла графа вызывается функция find_set, которая имеет трудоемкость O(N). И того - O(N^2). Функция find_set при этом вообще особо кривая. Не понятно что она должна вернуть в каком случае.

Ну и еще, вот эта структура выглядит очень плохо:
vector > G;
Ну потому что edge - это тоже pair и в результате, во всех этих second.first и second.second хрен разберешься. Отрефакторить можно, например, введением нормальной структуры для дуги (вместо пары). При этом, в эту же дугу стоит засунуть длину. Легко ли въехать где тут номер дуги, а где - ее длина?

Comments

Only authorized users can post comments.
Please, Log in or Sign up
B

C++ - Test 002. Constants

  • Result:16points,
  • Rating points-10
B

C++ - Test 001. The first program and data types

  • Result:46points,
  • Rating points-6
FL

C++ - Test 006. Enumerations

  • Result:80points,
  • Rating points4
Last comments
k
kmssrFeb. 8, 2024, 6:43 p.m.
Qt Linux - Lesson 001. Autorun Qt application under Linux как сделать автозапуск для флэтпака, который не даёт создавать файлы в ~/.config - вот это вопрос ))
Qt WinAPI - Lesson 007. Working with ICMP Ping in Qt Без строки #include <QRegularExpressionValidator> в заголовочном файле не работает валидатор.
EVA
EVADec. 25, 2023, 10:30 a.m.
Boost - static linking in CMake project under Windows Ошибка LNK1104 часто возникает, когда компоновщик не может найти или открыть файл библиотеки. В вашем случае, это файл libboost_locale-vc142-mt-gd-x64-1_74.lib из библиотеки Boost для C+…
J
JonnyJoDec. 25, 2023, 8:38 a.m.
Boost - static linking in CMake project under Windows Сделал всё по-как у вас, но выдаёт ошибку [build] LINK : fatal error LNK1104: не удается открыть файл "libboost_locale-vc142-mt-gd-x64-1_74.lib" Хоть убей, не могу понять в чём дел…
G
GvozdikDec. 18, 2023, 9:01 p.m.
Qt/C++ - Lesson 056. Connecting the Boost library in Qt for MinGW and MSVC compilers Для решения твой проблемы добавь в файл .pro строчку "LIBS += -lws2_32" она решит проблему , лично мне помогло.
Now discuss on the forum
AC
Alexandru CodreanuJan. 19, 2024, 11:57 a.m.
QML Обнулить значения SpinBox Доброго времени суток, не могу разобраться с обнулением значение SpinBox находящего в делегате. import QtQuickimport QtQuick.ControlsWindow { width: 640 height: 480 visible: tr…
BlinCT
BlinCTDec. 27, 2023, 8:57 a.m.
Растягивать Image на парент по высоте Ну и само собою дял включения scrollbar надо чтобы был Flickable. Так что выходит как то так Flickable{ id: root anchors.fill: parent clip: true property url linkFile p…
Дмитрий
ДмитрийJan. 10, 2024, 4:18 a.m.
Qt Creator загружает всю оперативную память Проблема решена. Удалось разобраться с помощью утилиты strace. Запустил ее: strace ./qtcreator Начал выводиться весь лог работы креатора. В один момент он начал считывать фай…
Evgenii Legotckoi
Evgenii LegotckoiDec. 12, 2023, 6:48 a.m.
Побуквенное сравнение двух строк Добрый день. Там случайно не высылается этот сигнал textChanged ещё и при форматировани текста? Если решиать в лоб, то можно просто отключать сигнал/слотовое соединение внутри слота и …

Follow us in social networks