W tym artykule omówimy algorytm Kruskala. Tutaj zobaczymy także złożoność, działanie, przykład i implementację algorytmu Kruskala.

Zanim jednak przejdziemy bezpośrednio do algorytmu, powinniśmy najpierw zrozumieć podstawowe pojęcia, takie jak drzewo opinające i minimalne drzewo opinające.

Drzewo rozpinające - Drzewo rozpinające jest podgrafem nieskierowanego, spójnego grafu.

Minimalne drzewo rozpinające - Minimalne drzewo rozpinające można zdefiniować jako drzewo rozpinające, w którym suma wag krawędzi jest minimalna. Ciężar drzewa rozpinającego jest sumą ciężarów nadanych krawędziom drzewa rozpinającego.

Zacznijmy teraz od głównego tematu.

Algorytm Kruskala służy do znalezienia minimalnego drzewa rozpinającego dla połączonego grafu ważonego. Głównym celem algorytmu jest znalezienie podzbioru krawędzi, za pomocą których możemy przejść przez każdy wierzchołek grafu. Kieruje się podejściem zachłannym, które polega na znajdowaniu optymalnego rozwiązania na każdym etapie, zamiast skupiać się na optymalnym globalnym.

Jak działa algorytm Kruskala?

W algorytmie Kruskala zaczynamy od krawędzi o najmniejszej wadze i dodajemy je aż do osiągnięcia celu. Etapy implementacji algorytmu Kruskala są wymienione w następujący sposób:

• Najpierw posortuj wszystkie krawędzie od niskiej wagi do wysokiej.
• Teraz weź krawędź o najniższej wadze i dodaj ją do drzewa rozpinającego. Jeśli dodana krawędź tworzy cykl, odrzuć ją.
• Kontynuuj dodawanie krawędzi, aż dotrzemy do wszystkich wierzchołków i zostanie utworzone minimalne drzewo rozpinające.

Zastosowania algorytmu Kruskala to:

• Algorytm Kruskala można wykorzystać do rozmieszczenia przewodów elektrycznych pomiędzy miastami.
• Można go używać do ustanawiania połączeń LAN.

Przykład algorytmu Kruskala

Przyjrzyjmy się teraz działaniu algorytmu Kruskala na przykładzie. Algorytm Kruskala łatwiej będzie zrozumieć na przykładzie.

Załóżmy, że wykres ważony to -

Wagę krawędzi powyższego wykresu podaje poniższa tabela -

Teraz posortuj krawędzie podane powyżej w kolejności rosnącej według ich wag.

Zacznijmy teraz konstruować minimalne drzewo rozpinające.

dekodowanie javascript base64

Krok 1 - Najpierw dodaj krawędź AB z wagą 1 do MST.

Krok 2 - Dodaj krawędź Z z wagą 2 do MST, ponieważ nie tworzy on cyklu.

Krok 3 - Dodaj krawędź pne z wagą 3 do MST, ponieważ nie tworzy on żadnego cyklu ani pętli.

Krok 4 - Teraz wybierz krawędź płyta CD z wagą 4 do MST, ponieważ nie tworzy on cyklu.

Krok 5 - Następnie wybierz krawędź ALE z wagą 5. Uwzględnienie tej krawędzi utworzy cykl, więc odrzuć ją.

Krok 6 - Wybierz krawędź AC z wagą 7. Uwzględnienie tej krawędzi utworzy cykl, więc odrzuć ją.

Krok 7 - Wybierz krawędź OGŁOSZENIE z wagą 10. Uwzględnienie tej krawędzi również utworzy cykl, więc odrzuć ją.

Zatem ostateczne minimalne drzewo rozpinające uzyskane z danego grafu ważonego przy użyciu algorytmu Kruskala to -

Koszt MST wynosi = AB + DE + BC + CD = 1 + 2 + 3 + 4 = 10.

Teraz liczba krawędzi w powyższym drzewie jest równa liczbie wierzchołków minus 1. Zatem algorytm zatrzymuje się w tym miejscu.

Algorytm

 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 

Złożoność algorytmu Kruskala

Przyjrzyjmy się teraz złożoności czasowej algorytmu Kruskala.

Złożoność czasu
Złożoność czasowa algorytmu Kruskala wynosi O(E logE) lub O(V logV), gdzie E jest liczbą nie. krawędzi, a V to nr. wierzchołków.

Implementacja algorytmu Kruskala

Przyjrzyjmy się teraz implementacji algorytmu Kruskala.

Program: Napisz program implementujący algorytm Kruskala w języku 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>