In dit artikel bespreken we het algoritme van Kruskal. Hier zullen we ook de complexiteit, werking, voorbeeld en implementatie van het Kruskal-algoritme zien.
Maar voordat we rechtstreeks naar het algoritme gaan, moeten we eerst de basistermen begrijpen, zoals spanning tree en minimum spanning tree.
Overspannende boom - Een spanning tree is de subgraaf van een ongerichte verbonden graaf.
Minimaal overspannende boom - De minimaal opspannende boom kan worden gedefinieerd als de opspannende boom waarin de som van de gewichten van de rand minimaal is. Het gewicht van de opspannende boom is de som van de gewichten die aan de randen van de opspannende boom worden gegeven.
Laten we nu beginnen met het hoofdonderwerp.
Het algoritme van Kruskal wordt gebruikt om de minimaal opspannende boom voor een verbonden gewogen grafiek te vinden. Het hoofddoel van het algoritme is het vinden van de subset van randen waarmee we elk hoekpunt van de grafiek kunnen doorkruisen. Het volgt de hebzuchtige aanpak die in elke fase een optimale oplossing vindt, in plaats van zich te concentreren op een mondiaal optimale oplossing.
Hoe werkt het algoritme van Kruskal?
In het algoritme van Kruskal beginnen we bij randen met het laagste gewicht en blijven we de randen toevoegen totdat het doel is bereikt. De stappen om het algoritme van Kruskal te implementeren worden als volgt weergegeven:
- Sorteer eerst alle randen van laag gewicht naar hoog.
- Neem nu de rand met het laagste gewicht en voeg deze toe aan de opspannende boom. Als de toe te voegen rand een cyclus creëert, verwerp dan de rand.
- Ga door met het toevoegen van de randen totdat we alle hoekpunten hebben bereikt en er een minimaal opspannende boom is gemaakt.
De toepassingen van het algoritme van Kruskal zijn -
- Het algoritme van Kruskal kan worden gebruikt om elektrische bedrading tussen steden aan te leggen.
- Het kan worden gebruikt om LAN-verbindingen tot stand te brengen.
Voorbeeld van het algoritme van Kruskal
Laten we nu de werking van het algoritme van Kruskal bekijken aan de hand van een voorbeeld. Het zal gemakkelijker zijn om het algoritme van Kruskal te begrijpen aan de hand van een voorbeeld.
Stel dat een gewogen grafiek is -
Het gewicht van de randen van de bovenstaande grafiek wordt gegeven in de onderstaande tabel -
| Rand | AB | AC | ADVERTENTIE | MAAR | BC | CD | VAN |
| Gewicht | 1 | 7 | 10 | 5 | 3 | 4 | 2 |
Sorteer nu de hierboven gegeven randen in oplopende volgorde van hun gewicht.
| Rand | AB | VAN | BC | CD | MAAR | AC | ADVERTENTIE |
| Gewicht | 1 | 2 | 3 | 4 | 5 | 7 | 10 |
Laten we nu beginnen met het construeren van de minimaal opspannende boom.
c++ ingesteld
Stap 1 - Voeg eerst de rand toe AB met gewicht 1 naar het MST.
Stap 2 - Voeg de rand toe VAN met gewicht 2 aan de MST omdat deze de cyclus niet creëert.
Stap 3 - Voeg de rand toe BC met gewicht 3 naar de MST, omdat deze geen cyclus of lus creëert.
Stap 4 - Kies nu de rand CD met gewicht 4 aan de MST, omdat deze niet de cyclus vormt.
Stap 5 - Kies daarna de rand MAAR met gewicht 5. Als u deze rand opneemt, ontstaat er een cyclus, dus gooi deze weg.
Stap 6 - Kies de rand AC met gewicht 7. Als u deze rand opneemt, ontstaat er een cyclus, dus gooi deze weg.
Stap 7 - Kies de rand ADVERTENTIE met gewicht 10. Als je deze rand opneemt, ontstaat er ook een cyclus, dus gooi deze weg.
Dus de uiteindelijke minimaal opspannende boom verkregen uit de gegeven gewogen grafiek met behulp van het algoritme van Kruskal is -
De kosten van de MST zijn = AB + DE + BC + CD = 1 + 2 + 3 + 4 = 10.
Nu is het aantal randen in de bovenstaande boom gelijk aan het aantal hoekpunten minus 1. Het algoritme stopt hier dus.
Algoritme
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
Complexiteit van het algoritme van Kruskal
Laten we nu eens kijken naar de tijdscomplexiteit van het algoritme van Kruskal.
De tijdscomplexiteit van het algoritme van Kruskal is O(E logE) of O(V logV), waarbij E het nee is. van randen, en V is het nee. van hoekpunten.
Implementatie van het algoritme van Kruskal
Laten we nu eens kijken naar de implementatie van het algoritme van Kruskal.
Programma: Schrijf een programma om het algoritme van Kruskal in C++ te implementeren.
#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>