TechCodeview

V tomto článku se budeme zabývat Kruskalovým algoritmem. Zde také uvidíme složitost, fungování, příklad a implementaci Kruskalova algoritmu.

Než se však přesuneme přímo k algoritmu, měli bychom nejprve porozumět základním pojmům, jako je kostra a minimální kostra.

Spanning tree - Kostra je podgraf neorientovaného souvislého grafu.

Minimální kostra - Minimální kostru lze definovat jako kostru, ve které je součet vah hrany minimální. Hmotnost kostry je součtem vah daných okrajům kostry.

Nyní začněme hlavním tématem.

Kruskalův algoritmus se používá k nalezení minimální kostry pro spojený vážený graf. Hlavním cílem algoritmu je najít podmnožinu hran, pomocí kterých můžeme procházet každým vrcholem grafu. Řídí se chamtivým přístupem, který nalézá optimální řešení v každé fázi místo toho, aby se zaměřoval na globální optimum.

Jak funguje Kruskalův algoritmus?

V Kruskalově algoritmu začínáme od hran s nejnižší váhou a přidáváme hrany, dokud není dosaženo cíle. Kroky k implementaci Kruskalova algoritmu jsou uvedeny následovně -

• Nejprve seřaďte všechny hrany od nízké hmotnosti po vysokou.
• Nyní vezměte hranu s nejnižší hmotností a přidejte ji do kostry. Pokud hrana, která se má přidat, vytvoří cyklus, pak hranu odmítněte.
• Pokračujte v přidávání hran, dokud nedosáhneme všech vrcholů a nevytvoří se minimální kostra.

Aplikace Kruskalova algoritmu jsou -

• Kruskalův algoritmus lze použít k rozmístění elektrických rozvodů mezi městy.
• Lze jej použít k vytvoření připojení k síti LAN.

Příklad Kruskalova algoritmu

Nyní se podívejme na fungování Kruskalova algoritmu na příkladu. Kruskalův algoritmus bude snazší pochopit na příkladu.

Předpokládejme, že vážený graf je -

Váha hran výše uvedeného grafu je uvedena v níže uvedené tabulce -

Nyní seřaďte výše uvedené hrany ve vzestupném pořadí jejich hmotností.

Nyní začněme konstruovat minimální kostru.

tiskové pole v Javě

Krok 1 - Nejprve přidejte okraj AB s váhou 1 do MST.

Krok 2 - Přidejte okraj Z s váhou 2 na MST, protože nevytváří cyklus.

Krok 3 - Přidejte okraj před naším letopočtem s váhou 3 na MST, protože nevytváří žádný cyklus nebo smyčku.

Krok 4 - Nyní vyberte okraj CD s váhou 4 na MST, protože netvoří cyklus.

Krok 5 - Poté vyberte okraj ALE s váhou 5. Zahrnutím této hrany vytvoříte cyklus, takže jej zahoďte.

Krok 6 - Vyberte okraj AC s váhou 7. Zahrnutím této hrany vytvoříte cyklus, takže jej zahoďte.

Krok 7 - Vyberte okraj INZERÁT s váhou 10. Zahrnutím této hrany také vytvoříte cyklus, takže jej zahoďte.

Takže konečný minimální kostra získaný z daného váženého grafu pomocí Kruskalova algoritmu je -

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

Nyní se počet hran ve výše uvedeném stromu rovná počtu vrcholů mínus 1. Algoritmus se tedy zde 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 

Složitost Kruskalova algoritmu

Nyní se podívejme na časovou složitost Kruskalova algoritmu.

Časová složitost
Časová složitost Kruskalova algoritmu je O(E logE) nebo O(V logV), kde E je číslo. hran a V je ne. z vrcholů.

Implementace Kruskalova algoritmu

Nyní se podívejme na implementaci kruskalova algoritmu.

Program: Napište program pro implementaci kruskalova 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>