I denne artikkelen skal vi diskutere Kruskals algoritme. Her vil vi også se kompleksiteten, virkemåten, eksempelet og implementeringen av Kruskals algoritme.
Men før vi går direkte mot algoritmen, bør vi først forstå de grunnleggende begrepene som spenntre og minimum spenntre.
Spanning tre - Et spenningstre er undergrafen til en urettet tilkoblet graf.
Minimum spannende tre - Minimum spenntre kan defineres som spenntreet der summen av vektene til kanten er minimum. Vekten til spenntreet er summen av vektene gitt til kantene på spenntreet.
La oss nå starte med hovedemnet.
Kruskals algoritme brukes til å finne minimumspenningstreet for en tilkoblet vektet graf. Hovedmålet til algoritmen er å finne undergruppen av kanter ved å bruke som vi kan krysse hvert toppunkt i grafen. Den følger den grådige tilnærmingen som finner en optimal løsning på alle trinn i stedet for å fokusere på et globalt optimum.
Hvordan fungerer Kruskals algoritme?
I Kruskals algoritme starter vi fra kanter med lavest vekt og fortsetter å legge til kantene til målet er nådd. Trinnene for å implementere Kruskals algoritme er oppført som følger -
- Sorter først alle kantene fra lav vekt til høy.
- Ta nå kanten med den laveste vekten og legg den til spenntreet. Hvis kanten som skal legges til skaper en syklus, avvis kanten.
- Fortsett å legge til kantene til vi når alle toppunkter, og et minimumsspennende tre er opprettet.
Applikasjonene til Kruskals algoritme er -
- Kruskals algoritme kan brukes til å legge ut elektriske ledninger mellom byer.
- Den kan brukes til å legge ned LAN-tilkoblinger.
Eksempel på Kruskals algoritme
La oss nå se hvordan Kruskals algoritme fungerer ved å bruke et eksempel. Det vil være lettere å forstå Kruskals algoritme ved å bruke et eksempel.
Anta at en vektet graf er -
Vekten av kantene på grafen ovenfor er gitt i tabellen nedenfor -
| Kant | AB | AC | AD | MEN | f.Kr | CD | AV |
| Vekt | 1 | 7 | 10 | 5 | 3 | 4 | 2 |
Sorter nå kantene gitt ovenfor i stigende rekkefølge etter vektene deres.
| Kant | AB | AV | f.Kr | CD | MEN | AC | AD |
| Vekt | 1 | 2 | 3 | 4 | 5 | 7 | 10 |
La oss nå begynne å konstruere minimumspenningstreet.
java visualizer
Trinn 1 - Først legger du til kanten AB med vekt 1 til MST.
Steg 2 - Legg til kanten AV med vekt 2 til MST siden den ikke skaper syklusen.
Trinn 3 - Legg til kanten f.Kr med vekt 3 til MST, siden den ikke skaper noen syklus eller løkke.
Trinn 4 - Velg kanten nå CD med vekt 4 til MST, siden den ikke danner syklusen.
Trinn 5 - Etter det velger du kanten MEN med vekt 5. Å inkludere denne kanten vil skape syklusen, så kast den.
Trinn 6 - Velg kanten AC med vekt 7. Å inkludere denne kanten vil skape syklusen, så kast den.
Trinn 7 - Velg kanten AD med vekt 10. Å inkludere denne kanten vil også skape syklusen, så kast den.
Så det endelige minimumspenningstreet oppnådd fra den gitte vektede grafen ved å bruke Kruskals algoritme er -
Kostnaden for MST er = AB + DE + BC + CD = 1 + 2 + 3 + 4 = 10.
Nå er antallet kanter i treet ovenfor lik antall toppunkter minus 1. Så algoritmen stopper her.
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
Kompleksiteten til Kruskals algoritme
La oss nå se tidskompleksiteten til Kruskals algoritme.
Tidskompleksiteten til Kruskals algoritme er O(E logE) eller O(V logV), der E er nr. av kanter, og V er nr. av hjørner.
Implementering av Kruskals algoritme
La oss nå se implementeringen av Kruskals algoritme.
Program: Skriv et program for å implementere kruskals algoritme 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>