logo

TechCodeview

Kruskalov algoritmus

V tomto článku budeme diskutovať o Kruskalovom algoritme. Tu tiež uvidíme zložitosť, fungovanie, príklad a implementáciu Kruskalovho algoritmu.

Ale predtým, než prejdeme priamo k algoritmu, mali by sme najprv pochopiť základné pojmy, ako je kostra a minimálna kostra.

Spanning tree - Kostra je podgrafom neorientovaného súvislého grafu.

Minimálny kostrový strom - Minimálny kostra môže byť definovaná ako kostra, v ktorej je súčet váh hrany minimálny. Hmotnosť kostry je súčet váh pridelených okrajom kostry.

Teraz začnime s hlavnou témou.

Kruskalov algoritmus sa používa na nájdenie minimálneho kostry pre spojený vážený graf. Hlavným cieľom algoritmu je nájsť podmnožinu hrán, pomocou ktorých môžeme prejsť každým vrcholom grafu. Riadi sa chamtivým prístupom, ktorý nachádza optimálne riešenie v každej fáze namiesto zamerania sa na globálne optimum.

Ako funguje Kruskalov algoritmus?

V Kruskalovom algoritme začíname od hrán s najnižšou váhou a stále pridávame hrany, až kým nedosiahneme cieľ. Kroky na implementáciu Kruskalovho algoritmu sú uvedené nasledovne -

  • Najprv zoraďte všetky okraje od nízkej hmotnosti po vysokú.
  • Teraz vezmite okraj s najnižšou hmotnosťou a pridajte ho na kostru. Ak hrana, ktorá sa má pridať, vytvorí cyklus, potom hranu odmietnite.
  • Pokračujte v pridávaní hrán, kým nedosiahneme všetky vrcholy a nevytvorí sa minimálny kostra.

Aplikácie Kruskalovho algoritmu sú -

  • Kruskalov algoritmus možno použiť na rozloženie elektrických rozvodov medzi mestami.
  • Môže sa použiť na vytvorenie pripojení LAN.

Príklad Kruskalovho algoritmu

Teraz sa pozrime na fungovanie Kruskalovho algoritmu na príklade. Na príklade bude jednoduchšie pochopiť Kruskalov algoritmus.

Predpokladajme, že vážený graf je -

Kruskal

Hmotnosť hrán vyššie uvedeného grafu je uvedená v tabuľke nižšie -

Hrana AB AC AD ALE BC CD OF
Hmotnosť 1 7 10 5 3 4 2

Teraz zoraďte okraje uvedené vyššie vo vzostupnom poradí ich hmotnosti.

Hrana AB OF BC CD ALE AC AD
Hmotnosť 1 2 3 4 5 7 10

Teraz začnime s konštrukciou minimálneho kostry.

bublinový druh pytóna

Krok 1 - Najprv pridajte okraj AB s hmotnosťou 1 na MST.

Kruskal

Krok 2 - Pridajte okraj OF s hmotnosťou 2 na MST, pretože nevytvára cyklus.

Kruskal

Krok 3 - Pridajte okraj BC s hmotnosťou 3 na MST, pretože nevytvára žiadny cyklus ani slučku.

Kruskal

Krok 4 - Teraz vyberte okraj CD s hmotnosťou 4 na MST, keďže netvorí cyklus.

Kruskal

Krok 5 - Potom vyberte okraj ALE s hmotnosťou 5. Zahrnutím tejto hrany vytvoríte cyklus, preto ho zahoďte.

Krok 6 - Vyberte okraj AC s hmotnosťou 7. Zahrnutím tejto hrany vytvoríte cyklus, preto ho zahoďte.

Krok 7 - Vyberte okraj AD s hmotnosťou 10. Zahrnutím tejto hrany tiež vytvoríte cyklus, takže ho zahoďte.

Takže konečný minimálny kostra získaná z daného váženého grafu pomocou Kruskalovho algoritmu je -

Kruskal

Cena MST je = AB + DE + BC + CD = 1 + 2 + 3 + 4 = 10.

Teraz sa počet hrán vo vyššie uvedenom strome rovná počtu vrcholov mínus 1. Algoritmus sa tu teda zastaví.

Algoritmus

 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

Zložitosť Kruskalovho algoritmu

Teraz sa pozrime na časovú zložitosť Kruskalovho algoritmu.

    Časová zložitosť
    Časová zložitosť Kruskalovho algoritmu je O(E logE) alebo O(V logV), kde E je číslo. hrán a V je č. z vrcholov.

Implementácia Kruskalovho algoritmu

Teraz sa pozrime na implementáciu kruskalovho algoritmu.

Program: Napíšte program na implementáciu kruskalovho algoritmu v 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>