Алгоритм Борувки

#include <iostream>

using namespace std;

struct Edge// структура для представления взвешенного ребра в графе
{
    int src;
    int dest;
    int weight;
};
struct Graph // структура для представления подключенной, ненаправленной и взвешенный граф как набор ребер.
{
    int V;// V->Количество вершин,
    int E;// E->Количество ребер
    Edge* edge;
};
struct subset // Структура для представления подмножества для union-find
{
    int parent;
    int rank;
};
// Прототипы функций для union-find (Эти функции определены после борувкаМСТ ())
int find(struct subset subsets[], int i);
void Union(struct subset subsets[], int x, int y);
void boruvkaMST(struct Graph* graph)// Основная функция для MST с использованием алгоритма Борувки
{
    int V = graph->V, E = graph->E; Edge* edge = graph->edge;// Получить данные данного графика
    struct subset* subsets = new subset[V];// Выделить память для создания V подмножеств.
    int* cheapest = new int[V];// Массив для хранения индекса самого дешевого края
    //подмножество. Сохраненный индекс для индексации массива 'edge []'
    for (int v = 0; v < V; ++v) // Создать V подмножеств с отдельными элементами
    {
        subsets[v].parent = v;
        subsets[v].rank = 0;
        cheapest[v] = -1;
    }
    // Изначально существует V разных деревьев. Наконец, будет одно дерево, которое будет MST
    int numTrees = V;
    int MSTweight = 0;
    // Продолжаем комбинировать компоненты (или наборы), пока все Компоненты не объединяются в один MST.
    while (numTrees > 1)
    {
        for (int v = 0; v < V; ++v)// Каждый раз инициализируем самый дешевый массив
            cheapest[v] = -1;
        for (int i = 0; i < E; i++)// Пройдите через все ребра и обновите самый дешевый из каждого компонента
        {
            // Найти компоненты (или наборы) двух углов текущего края
            int set1 = find(subsets, edge[i].src);
            int set2 = find(subsets, edge[i].dest);
            if (set1 == set2) // Если два угла текущего ребра принадлежат тот же набор, игнорировать текущее ребро
                continue;
            // Иначе проверяем, находится ли текущий фронт ближе к предыдущему
            // самые дешевые ребра set1 и set2
            else
            {
                if (cheapest[set1] == -1 || edge[cheapest[set1]].weight > edge[i].weight)
                     cheapest[set1] = i;
                if (cheapest[set2] == -1 ||edge[cheapest[set2]].weight > edge[i].weight)
                     cheapest[set2] = i;
            }
        }
        for (int i = 0; i < V; i++)// Рассмотрим выбранные выше самые дешевые ребра и добавим их в MST
        {
            if (cheapest[i] != -1)// Проверяем, существует ли самый дешевый для текущего набора
            {
                int set1 = find(subsets, edge[cheapest[i]].src);
                int set2 = find(subsets, edge[cheapest[i]].dest);
                if (set1 == set2)
                    continue;
                MSTweight += edge[cheapest[i]].weight;
                printf("Edge %d-%d included in MST\n",
                edge[cheapest[i]].src, edge[cheapest[i]].dest);
                Union(subsets, set1, set2);// Делаем объединение set1 и set2 и уменьшаем число деревьев
                numTrees--;
            }
        }
    }
    printf("Weight of MST is %d\n", MSTweight);
    return;
}
struct Graph* createGraph(int V, int E) // Создаем граф с V вершинами и E ребрами
{
    Graph* graph = new Graph;
    graph->V = V;
    graph->E = E;
    graph->edge = new Edge[E];
    return graph;
}
int find(struct subset subsets[], int i) // Полезная функция для поиска множества элементов i (использует технику сжатия пути)
{
    if (subsets[i].parent != i) // найти root и сделать root родителем i (сжатие пути)
        subsets[i].parent = find(subsets, subsets[i].parent);
    return subsets[i].parent;
}
void Union(struct subset subsets[], int x, int y) // Функция, которая объединяет два набора x и y (использует объединение по рангу)
{
    int xroot = find(subsets, x);
    int yroot = find(subsets, y);
    // Прикрепить дерево меньшего ранга под корень высокого  ранговое дерево (объединение по рангу)
    if (subsets[xroot].rank < subsets[yroot].rank)
        subsets[xroot].parent = yroot;
    else if (subsets[xroot].rank > subsets[yroot].rank)
        subsets[yroot].parent = xroot;
    else// Если ранги одинаковы, то создайте их как root и  увеличиваем ранг на единицу
    {
        subsets[yroot].parent = xroot;
        subsets[xroot].rank++;
    }
}
// Программа драйвера для проверки вышеуказанных функций
int main()
{
    int V = 4;  // Количество вершин в графе
    int E = 5;  // Количество ребер в графе
    struct Graph* graph = createGraph(V, E);
    graph->edge[0].src = 0; graph->edge[0].dest = 1; graph->edge[0].weight = 10;// добавляем ребро 0-1
    graph->edge[1].src = 0; graph->edge[1].dest = 2; graph->edge[1].weight = 6;// добавляем ребро 0-2
    graph->edge[2].src = 0; graph->edge[2].dest = 3; graph->edge[2].weight = 5;// добавляем ребро 0-3
    graph->edge[3].src = 1;graph->edge[3].dest = 3;graph->edge[3].weight = 15;// добавить ребро 1-3
    graph->edge[4].src = 2;graph->edge[4].dest = 3;graph->edge[4].weight = 100;// добавить ребро 2-3

    boruvkaMST(graph);

    return 0;
}