logo

TechCodeview

Kruskal's Algorithm

В тази статия ще обсъдим алгоритъма на Kruskal. Тук също ще видим сложността, работата, примера и изпълнението на алгоритъма на Kruskal.

Но преди да преминем директно към алгоритъма, първо трябва да разберем основните термини като spanning tree и minimal spanning tree.

Spanning Tree - Обхващащото дърво е подграф на неориентиран свързан граф.

Минимално обхващащо дърво - Минималното обхващащо дърво може да се дефинира като обхващащо дърво, в което сумата от теглата на ръба е минимална. Теглото на обхващащото дърво е сумата от теглата, дадени на ръбовете на обхващащото дърво.

Сега да започнем с основната тема.

Kruskal's Algorithm се използва за намиране на минималното обхващащо дърво за свързан претеглен график. Основната цел на алгоритъма е да намери подмножеството от ръбове, чрез които можем да обходим всеки връх на графиката. Той следва алчния подход, който намира оптимално решение на всеки етап, вместо да се фокусира върху глобален оптимум.

Как работи алгоритъмът на Kruskal?

В алгоритъма на Kruskal започваме от ръбове с най-ниско тегло и продължаваме да добавяме ръбовете, докато целта бъде достигната. Стъпките за прилагане на алгоритъма на Kruskal са изброени както следва -

  • Първо сортирайте всички ръбове от ниско тегло към високо.
  • Сега вземете ръба с най-ниско тегло и го добавете към обхващащото дърво. Ако ръбът, който трябва да се добави, създава цикъл, тогава отхвърлете ръба.
  • Продължете да добавяте ръбовете, докато достигнем всички върхове и се създаде минимално обхващащо дърво.

Приложенията на алгоритъма на Kruskal са -

  • Алгоритъмът на Kruskal може да се използва за оформление на електрически кабели между градовете.
  • Може да се използва за установяване на LAN връзки.

Пример за алгоритъм на Kruskal

Сега, нека видим работата на алгоритъма на Крускал, използвайки пример. Ще бъде по-лесно да разберете алгоритъма на Kruskal, като използвате пример.

Да предположим, че една претеглена графика е -

Kruskal

Теглото на ръбовете на горната графика е дадено в таблицата по-долу -

Ръб, край AB AC AD НО пр.н.е CD НА
Тегло 1 7 10 5 3 4 2

Сега сортирайте ръбовете, дадени по-горе, във възходящ ред на техните тегла.

Ръб, край AB НА пр.н.е CD НО AC AD
Тегло 1 2 3 4 5 7 10

Сега нека започнем да конструираме минималното обхващащо дърво.

java локална дата и час

Етап 1 - Първо добавете ръба AB с тегло 1 към MST.

Kruskal

Стъпка 2 - Добавете ръба НА с тегло 2 към MST, тъй като не създава цикъла.

Kruskal

Стъпка 3 - Добавете ръба пр.н.е с тегло 3 към MST, тъй като не създава никакъв цикъл или цикъл.

Kruskal

Стъпка 4 - Сега изберете ръба CD с тегло 4 към MST, тъй като не формира цикъла.

Kruskal

Стъпка 5 - След това изберете ръба НО с тегло 5. Включването на този ръб ще създаде цикъла, така че го изхвърлете.

Стъпка 6 - Изберете ръба AC с тегло 7. Включването на този ръб ще създаде цикъла, така че го изхвърлете.

Стъпка 7 - Изберете ръба AD с тегло 10. Включването на този ръб също ще създаде цикъла, така че го изхвърлете.

И така, крайното минимално обхващащо дърво, получено от дадената претеглена графика с помощта на алгоритъма на Kruskal е -

Kruskal

Цената на 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

Сложност на алгоритъма на Крускал

Сега нека видим времевата сложност на алгоритъма на Крускал.

    Времева сложност
    Времевата сложност на алгоритъма на Kruskal е O(E logE) или O(V logV), където E е номерът. на ръбовете, а V е номерът. от върхове.

Реализация на алгоритъма на Крускал

Сега нека видим изпълнението на алгоритъма на Kruskal.

програма: Напишете програма за прилагане на алгоритъма на 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 &gt;&gt; edges; for(int i = 0;i <edges;++i) { cout<> x &gt;&gt; y &gt;&gt; weight; p[i] = make_pair(weight, make_pair(x, y)); } sort(p, p + edges); minimumCost = kruskal(p); cout &lt;<'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&apos;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>