У цій статті ми обговоримо алгоритм Крускала. Тут ми також побачимо складність, роботу, приклад і реалізацію алгоритму Крускала.
Але перш ніж перейти безпосередньо до алгоритму, ми повинні спочатку зрозуміти основні терміни, такі як охоплююче дерево та мінімальне остовне дерево.
Остовне дерево - Остовне дерево — це підграф неорієнтованого зв’язного графа.
Мінімальне охоплююче дерево - Мінімальне остовне дерево можна визначити як остовне дерево, в якому сума ваг ребра мінімальна. Вага остовного дерева - це сума ваг, наданих ребрам остовного дерева.
А тепер почнемо з основної теми.
Алгоритм Крускала використовується для знаходження мінімального остовного дерева для зв’язного зваженого графа. Основна мета алгоритму — знайти підмножину ребер, за допомогою якої можна обійти кожну вершину графа. Він дотримується жадібного підходу, який знаходить оптимальне рішення на кожному етапі замість зосередження на глобальному оптимумі.
Як працює алгоритм Крускала?
В алгоритмі Крускала ми починаємо з ребер із найменшою вагою та продовжуємо додавати ребра, доки не буде досягнуто мети. Кроки для реалізації алгоритму Крускала перераховані наступним чином:
- Спочатку відсортуйте всі краї від низької ваги до високої.
- Тепер візьміть ребро з найменшою вагою та додайте його до остовного дерева. Якщо ребро, яке потрібно додати, створює цикл, тоді відхиліть ребро.
- Продовжуйте додавати ребра, доки не досягнемо всіх вершин і не буде створено мінімальне остовне дерево.
Застосування алгоритму Крускала:
- Алгоритм Крускала можна використовувати для розкладки електропроводки між містами.
- Його можна використовувати для підключення до локальної мережі.
Приклад алгоритму Крускала
Тепер давайте подивимося на прикладі роботи алгоритму Крускала. На прикладі буде легше зрозуміти алгоритм Крускала.
Припустимо, що зважений графік -
Вага ребер наведеного вище графа наведена в таблиці нижче -
| Край | АВ | AC | нашої ери | АЛЕ | е | CD | OF |
| вага | 1 | 7 | 10 | 5 | 3 | 4 | 2 |
Тепер відсортуйте наведені вище ребра в порядку зростання їх ваг.
| Край | АВ | OF | е | CD | АЛЕ | AC | нашої ери |
| вага | 1 | 2 | 3 | 4 | 5 | 7 | 10 |
Тепер почнемо будувати мінімальне остовне дерево.
круговий розклад
Крок 1 - Спочатку додайте край АВ з вагою 1 до МСТ.
Крок 2 - Додайте край OF з вагою 2 до MST, оскільки він не створює цикл.
Крок 3 - Додайте край е з вагою 3 до MST, оскільки він не створює жодного циклу чи циклу.
Крок 4 - Тепер виберіть край CD з вагою 4 до MST, оскільки він не формує цикл.
Крок 5 - Після цього підберіть край АЛЕ з вагою 5. Включення цього краю створить цикл, тому відкиньте його.
Крок 6 - Виберіть край AC з вагою 7. Включення цього краю створить цикл, тому відкиньте його.
Крок 7 - Виберіть край нашої ери з вагою 10. Включення цього краю також створить цикл, тому відкиньте його.
Таким чином, остаточне мінімальне остовне дерево, отримане з даного зваженого графа за допомогою алгоритму Крускала, є -
Вартість MST = AB + DE + BC + CD = 1 + 2 + 3 + 4 = 10.
Тепер кількість ребер у наведеному вище дереві дорівнює кількості вершин мінус 1. Отже, алгоритм зупиняється на цьому.
Алгоритм
Step 1: Create a forest F in such a way that every vertex of the graph is a separate tree. Step 2: Create a set E that contains all the edges of the graph. Step 3: Repeat Steps 4 and 5 while E is NOT EMPTY and F is not spanning Step 4: Remove an edge from E with minimum weight Step 5: IF the edge obtained in Step 4 connects two different trees, then add it to the forest F (for combining two trees into one tree). ELSE Discard the edge Step 6: END
Складність алгоритму Крускала
Тепер давайте подивимося на часову складність алгоритму Крускала.
Часова складність алгоритму Крускала становить O(E logE) або O(V logV), де E – номер. ребер, а V – номер. вершин.
Реалізація алгоритму Крускала
Тепер давайте подивимося реалізацію алгоритму Kruskal.
програма: Напишіть програму для реалізації алгоритму Крускала на C++.
#include #include using namespace std; const int MAX = 1e4 + 5; int id[MAX], nodes, edges; pair <long long, pair> p[MAX]; void init() { for(int i = 0;i <max;++i) id[i]="i;" } int root(int x) { while(id[x] !="x)" id[x]="id[id[x]];" x="id[x];" return x; void union1(int x, y) p="root(x);" q="root(y);" id[p]="id[q];" long kruskal(pair<long long, pair> p[]) { int x, y; long long cost, minimumCost = 0; for(int i = 0;i <edges;++i) { x="p[i].second.first;" y="p[i].second.second;" cost="p[i].first;" if(root(x) !="root(y))" minimumcost +="cost;" union1(x, y); } return minimumcost; int main() x, y; long weight, cost, init(); cout <> nodes >> edges; for(int i = 0;i <edges;++i) { cout<> x >> y >> weight; p[i] = make_pair(weight, make_pair(x, y)); } sort(p, p + edges); minimumCost = kruskal(p); cout <<'minimum cost is '<< minimumcost << endl; return 0; } < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/85/kruskals-algorithm-6.webp" alt="Kruskal"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <hr></'minimum></edges;++i)></edges;++i)></max;++i)></long>