I den här artikeln kommer vi att diskutera Kruskals algoritm. Här kommer vi också att se komplexiteten, arbetet, exemplet och implementeringen av Kruskals algoritm.
Men innan vi går direkt mot algoritmen bör vi först förstå de grundläggande termerna som spaning tree och minimum spaning tree.
Spanning Tree - Ett spännträd är subgrafen till en oriktad sammankopplad graf.
Minsta spännvidd träd - Minsta spännträd kan definieras som spännträdet där summan av kantens vikter är minimum. Vikten av spännträdet är summan av vikterna som ges till kanterna av spännträdet.
Låt oss nu börja med huvudämnet.
Kruskals algoritm används för att hitta det minsta spännträdet för en sammankopplad viktad graf. Det huvudsakliga målet för algoritmen är att hitta delmängden av kanter genom att använda vilken vi kan korsa varje vertex i grafen. Den följer den giriga strategin som hittar en optimal lösning i varje skede istället för att fokusera på ett globalt optimum.
Hur fungerar Kruskals algoritm?
I Kruskals algoritm utgår vi från kanter med lägst vikt och fortsätter att lägga till kanterna tills målet är nått. Stegen för att implementera Kruskals algoritm listas enligt följande -
- Sortera först alla kanter från låg vikt till hög.
- Ta nu kanten med den lägsta vikten och lägg till den i spännträdet. Om kanten som ska läggas till skapar en cykel, avvisa kanten.
- Fortsätt att lägga till kanterna tills vi når alla hörn och ett minsta spännträd skapas.
Tillämpningarna av Kruskals algoritm är -
- Kruskals algoritm kan användas för att lägga upp elektriska ledningar mellan städer.
- Den kan användas för att lägga ner LAN-anslutningar.
Exempel på Kruskals algoritm
Låt oss nu se hur Kruskals algoritm fungerar med ett exempel. Det blir lättare att förstå Kruskals algoritm med hjälp av ett exempel.
Antag att en viktad graf är -
Vikten av kanterna på grafen ovan anges i tabellen nedan -
| Kant | AB | AC | AD | MEN | före Kristus | CD | AV |
| Vikt | 1 | 7 | 10 | 5 | 3 | 4 | 2 |
Sortera nu kanterna ovan i stigande ordning efter deras vikter.
| Kant | AB | AV | före Kristus | CD | MEN | AC | AD |
| Vikt | 1 | 2 | 3 | 4 | 5 | 7 | 10 |
Låt oss nu börja konstruera det minsta spännträdet.
maskininlärningsmodeller
Steg 1 - Lägg först till kanten AB med vikt 1 till MST.
Steg 2 - Lägg till kanten AV med vikt 2 till MST eftersom det inte skapar cykeln.
Steg 3 - Lägg till kanten före Kristus med vikt 3 till MST, eftersom det inte skapar någon cykel eller loop.
Steg 4 - Välj nu kanten CD med vikt 4 till MST, eftersom det inte bildar cykeln.
Steg 5 - Efter det väljer du kanten MEN med vikt 5. Att inkludera denna kant kommer att skapa cykeln, så kassera den.
Steg 6 - Välj kanten AC med vikt 7. Att inkludera denna kant kommer att skapa cykeln, så kassera den.
Steg 7 - Välj kanten AD med vikt 10. Att inkludera denna kant kommer också att skapa cykeln, så kassera den.
Så det sista minsta spännträdet som erhålls från den givna viktade grafen genom att använda Kruskals algoritm är -
Kostnaden för MST är = AB + DE + BC + CD = 1 + 2 + 3 + 4 = 10.
Nu är antalet kanter i ovanstående träd lika med antalet hörn minus 1. Så, algoritmen stannar här.
Algoritm
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
Komplexiteten hos Kruskals algoritm
Låt oss nu se tidskomplexiteten hos Kruskals algoritm.
Tidskomplexiteten för Kruskals algoritm är O(E logE) eller O(V logV), där E är no. av kanter, och V är nr. av hörn.
Implementering av Kruskals algoritm
Låt oss nu se implementeringen av Kruskals algoritm.
Program: Skriv ett program för att implementera Kruskals algoritm i 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 >> 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>