Алгоритм Краскала

Дерево, Алгоритм, Tree

Содержание

Алгоритм Краскала - это алгоритм минимального остовного дерева, что принимает граф в качестве входных данных и находит подмножество ребер этого графа, который формирует дерево, включающее в себя каждую вершину, а также имеет минимальную сумму весов среди всех деревьев, которые могут быть сформированы из графа.

Как работает алгоритм Краскала

Он подпадает под класс алгоритмов, называемых «жадными» алгоритмами , которые находят локальный оптимум в надежде найти глобальный оптимум.

Мы начинаем с ребер с наименьшим весом и продолжаем добавлять ребра, пока не достигнем нашей цели.

Шаги для реализации алгоритма Краскала следующие:

  1. Сортировать все ребра от малого веса до высокого.
  2. Возьмите ребро с наименьшим весом и добавьте его в остовное дерево. Если добавление ребра создало цикл, то отклоните это ребро.
  3. Продолжайте добавлять ребра, пока не достигнете всех вершин.

Пример алгоритма Краскала

Алгоритм Краскала. Псевдокод.

Любой минимальный алгоритм остовного дерева вращается вокруг проверки, создает ли ребро цикл или нет.

Наиболее распространенный способ выяснить это - алгоритм Union FInd . Алгоритм Union-Find разделяет вершины на кластеры и позволяет нам проверить, принадлежат ли две вершины одному кластеру или нет, и, следовательно, решить создает ли добавление ребра цикл.

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

Реализация алгоритма Краскала в C ++

Ниже приведен код для реализации в C ++. Мы используем стандартные библиотеки шаблонов, чтобы сделать нашу работу проще и чище.

#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;
}

Когда мы запускаем программу, мы получаем вывод как:

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

Алгоритм Краскала vs Прима

Алгоритм Прима является еще одним популярным алгоритмом минимального остовного дерева, который использует другую логику для нахождения MST графа. Вместо того, чтобы начинать с ребра, алгоритм Прима начинается с вершины и продолжает добавлять ребра с наименьшим весом, которых нет в дереве, пока все вершины не будут покрыты.

Рекомендуем хостинг TIMEWEB
Рекомендуем хостинг TIMEWEB
Стабильный хостинг, на котором располагается социальная сеть EVILEG. Для проектов на Django рекомендуем VDS хостинг.
Поддержать автора Donate

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

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

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

Странной кажется идея запихивания графа в класс. Да и все равно можно выстрелить в ногу, вызвав 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 хрен разберешься. Отрефакторить можно, например, введением нормальной структуры для дуги (вместо пары). При этом, в эту же дугу стоит засунуть длину. Легко ли въехать где тут номер дуги, а где - ее длина?

Комментарии

Только авторизованные пользователи могут публиковать комментарии.
Пожалуйста, авторизуйтесь или зарегистрируйтесь
Как стать автором?

Внесите вклад в развитие сообщества EVILEG.

Узнайте, как стать автором сайта.

Изучить
Donate

Добрый день, Дорогие Пользователи !!!

Я Евгений Легоцкой, разработчик EVILEG. И это мой хобби-проект, который помогает учиться программированию другим программистам и разработчикам

Если сайт помог вам, и вы хотите также поддержать развитие сайта, то вы можете сделать пожертвование следующими способами

PayPalYandex.Money
Timeweb

Позвольте мне порекомендовать вам отличный хостинг, на котором расположен EVILEG.

В течение многих лет Timeweb доказывает свою стабильность.

Для проектов на Django рекомендую VDS хостинг

Посмотреть Хостинг Timeweb
5 июня 2020 г. 23:20
Алексей

C++ - Тест 004. Указатели, Массивы и Циклы

  • Результат:60баллов,
  • Очки рейтинга-1
5 июня 2020 г. 23:15
Алексей

C++ - Тест 001. Первая программа и типы данных

  • Результат:53баллов,
  • Очки рейтинга-4
V
5 июня 2020 г. 16:47
Vladzo

C++ - Тест 005. Структуры и Классы

  • Результат:83баллов,
  • Очки рейтинга4
Последние комментарии
6 июня 2020 г. 15:13
Владислав Меленчук

Как установить и настроить Django JET

Можно использовать six и оттуда импортировать unicode. Я так решил проблему) Но всё равно откатился обратно на админку джанги.
6 июня 2020 г. 11:20
BL4CK R4BBIT

Как установить и настроить Django JET

на Django >3+ работать не будет. Либо придется лезть внутрь и переопределять метод unicode . Либо писать декоратор
5 июня 2020 г. 10:52
progammist

Распознавание изображений на Python с помощью TensorFlow и Keras

Огромное спасибо за метериал, по-больше бы подобных статей (с подробным описанием работы и примерами применения) на тему современных технологий. Вопрос поразмышлять. На текущий момент реал…
5 июня 2020 г. 1:39
Евгений Легоцкой

Qt/C++ - Урок 091. Как написать кастомный делегат управляющий подсветкой строки в таблице

По-моему, смысла в этом нет особого. Если делегат будет игнорировать настройки таблицы, то это приведёт ещё к большему непониманию, что вообще происходит, для программиста, который после вас буд…
5 июня 2020 г. 1:34
IscanderChe

Qt/C++ - Урок 091. Как написать кастомный делегат управляющий подсветкой строки в таблице

Сижу, размышляю: можно ли переписать делегата так, чтобы независимо от настроек строк выделялись строки?
Сейчас обсуждают на форуме
u
6 июня 2020 г. 7:26
ubomj

Галерея изображений

delete
s
6 июня 2020 г. 1:54
shuric

Qt/C++ Определение положения курсора над действие(кнопкой) в QToolBar

Доброго дня. Возник вопрос - как можно определить что курсор находится над определенным действием(кнопкой) в qtoolbar ? mainwindow.cpp MainWindow::MainWi…
s
6 июня 2020 г. 0:45
shuric

Qt/C++ особенности QProxyStyle

Да, Вы правы. Код был скопирован с сайта (уже не помню с какого), но решил пойти по пути более легком. Пришлось переписать - кому интересно: использовал stackedWidget для пе…
5 июня 2020 г. 23:08
Алексей

Посоветуйте новичку (базы данных и Qt, что учить)

Блин, а я недавно купил Шлее Qt 5.10 :( С детства хотел стать программистом, баловался Паскалем, писал простенькие программки на Delphi, создавал движок на php, изучал C (забросил и перешел на п…
5 июня 2020 г. 13:09
IscanderChe

QPlainTextEdit настройка цвета фона

Вечер добрый. Пытаюсь настроить цвет фона QPlainTextEdit следующим образом: CodeEditor::CodeEditor(QWidget *parent) : QPlainTextEdit(parent){ ... QPalette::ColorRole role = bac…
О нас
Услуги
© EVILEG 2015-2020
Рекомендует хостинг TIMEWEB