Определение

Алгоритм Краскала - алгоритм поиска минимального остовного дерева во взвешенном графе.

---

Принцип работы алгоритма

Ниже представлены: граф - слева и его минимальное остовное дерево - справа.

Сначала берутся все рёбра графа и сортируются по возрастанию. Далее, пока не переберём все рёбра, производим следующие операции:

1. Берём ребро из сортированного списка.
2. Если добавление ребра не создаёт цикла, то добавляем его в дерево.

ИСХОДНЫЙ ГРАФ

--- # Сложность

Сложность алгоритма: $O(E * log_2 E)$, где $E$ - количество рёбер.

---

Псевдокод

 Алгоритм Краскала
    рёбра <- сортированный список рёбер графа    
    группы узлов <- СНП (Система непересекающихся подмножеств) 

    для ребра в рёбрах 
        если узел_1 и узел_2 из разных групп  
            то добавляем ребро в дерево
               объединяем группы узлов
               
    вернуть дерево

---

Реализация на Python

Аннотация:
kraskal - функция для нахождения минимального остовного дерева с помощью алгоритма Краскала.
edges - список всех ребер в графе (каждое ребро представлено кортежем из трех элементов: две вершины и вес ребра).
V - количество вершин в графе.
mst - общая стоимость минимального остовного дерева.
UF - объект класса UnionFind для управления компонентами связности.

def kraskal(edges, V):  
    mst = 0  
    UF = UnionFind(V)  
    edges = sorted(edges, key=lambda x: x[2])  
    
    for edge in edges:  
        if not(UF.same_set(edge[0], edge[1])):  
            mst += edge[2]  
            UF.union_set(edge[0], edge[1])  
            
    return mst

---

Олимпиадная реализация на C++

Аннотация:
kraskal - функция для нахождения минимального остовного дерева с помощью алгоритма Краскала.
edges - вектор всех ребер в графе (каждое ребро представлено вектором из трех элементов: две вершины и вес ребра).
vtx - количество вершин в графе.
mst - общая стоимость минимального остовного дерева.
UF - объект класса UnionFind для управления компонентами связности.

typedef vector<int> vi;

int kraskal(vector<vi> edges, int vtx) {
    int mst = 0;
    UnionFind UF(vtx);
    sort(edges.begin(), edges.end(), comp);
    
    for (vi edge : edges) {
        if (!UF.same_set(edge[0], edge[1])) {
            mst += edge[2];
            UF.union_set(edge[0], edge[1]);
        }
    }
    return mst;
}

---

Продуктовая реализация на C++

Аннотация:
Graph - класс, представляющий граф.
list_edges_graph - список всех ребер графа.
count_nodes_graph - количество вершин в графе.
kraskal_tree - объект, представляющий минимальное остовное дерево, в которое добавляются ребра.
tree_kraskal - метод, реализующий алгоритм Краскала для нахождения минимального остовного дерева.
null_vector - пустой вектор, используемый для возврата в случае ошибки.
edges - вектор всех ребер графа.
group_nodes - объект класса UnionFind для управления компонентами связности.
compare - функция сравнения двух ребер по их весу.
vertex - количество вершин в графе.

vector <Edge> Graph::tree_kraskal() {
    vector <Edge> null_vector;
    int vertex = count_nodes_graph;
    UnionFind group_nodes(vertex);
    vector <Edge> edges = list_edges_graph;
    
    sort(edges.begin(), edges.end(), compare);
    
    for (Edge edge : edges) {
        if (!group_nodes.same_set(edge.from, edge.to)) {
            kraskal_tree.append_edge(edge);
            group_nodes.union_set(edge.from, edge.to);
        }
    }
    return kraskal_tree.list_edges_tree;
}