I denne artikel vil vi diskutere Kruskals algoritme. Her vil vi også se kompleksiteten, arbejdet, eksemplet og implementeringen af Kruskals algoritme.
Men før vi bevæger os direkte mod algoritmen, bør vi først forstå de grundlæggende udtryk som spændingstræ og minimum spændingstræ.
Spændende træ - Et spændingstræ er undergrafen af en urettet forbundet graf.
Minimum spændvidde træ - Minimum spændingstræ kan defineres som spændingstræet, hvor summen af kantens vægte er minimum. Vægten af spændingstræet er summen af vægtene givet til kanterne af spændingstræet.
Lad os nu starte med hovedemnet.
Kruskals algoritme bruges til at finde minimumspændingstræet for en forbundet vægtet graf. Hovedmålet med algoritmen er at finde delmængden af kanter, ved hjælp af hvilken vi kan krydse hvert hjørne af grafen. Den følger den grådige tilgang, der finder en optimal løsning på alle stadier i stedet for at fokusere på et globalt optimum.
Hvordan virker Kruskals algoritme?
I Kruskals algoritme starter vi fra kanter med den laveste vægt og bliver ved med at tilføje kanterne indtil målet er nået. Trinene til at implementere Kruskals algoritme er angivet som følger -
- Sorter først alle kanter fra lav vægt til høj.
- Tag nu kanten med den laveste vægt og tilføj den til spændingstræet. Hvis kanten, der skal tilføjes, skaber en cyklus, så afvis kanten.
- Fortsæt med at tilføje kanterne, indtil vi når alle hjørner, og et minimumsspændende træ er oprettet.
Anvendelserne af Kruskals algoritme er -
- Kruskals algoritme kan bruges til at layoute elektriske ledninger blandt byer.
- Den kan bruges til at nedlægge LAN-forbindelser.
Eksempel på Kruskals algoritme
Lad os nu se hvordan Kruskals algoritme fungerer ved hjælp af et eksempel. Det bliver lettere at forstå Kruskals algoritme ved hjælp af et eksempel.
Antag at en vægtet graf er -
Vægten af kanterne på ovenstående graf er angivet i nedenstående tabel -
| Edge | AB | AC | AD | MEN | f.Kr | CD | AF |
| Vægt | 1 | 7 | 10 | 5 | 3 | 4 | 2 |
Sorter nu kanterne angivet ovenfor i stigende rækkefølge efter deres vægte.
| Edge | AB | AF | f.Kr | CD | MEN | AC | AD |
| Vægt | 1 | 2 | 3 | 4 | 5 | 7 | 10 |
Lad os nu begynde at konstruere minimumspændingstræet.
sed kommando
Trin 1 - Tilføj først kanten AB med vægt 1 til MST.
Trin 2 - Tilføj kanten AF med vægt 2 til MST, da det ikke skaber cyklussen.
Trin 3 - Tilføj kanten f.Kr med vægt 3 til MST, da den ikke skaber nogen cyklus eller loop.
Trin 4 - Vælg nu kanten CD med vægt 4 til MST, da det ikke danner cyklussen.
Trin 5 - Vælg derefter kanten MEN med vægt 5. At inkludere denne kant vil skabe cyklussen, så kasser den.
Trin 6 - Vælg kanten AC med vægt 7. At inkludere denne kant vil skabe cyklussen, så kasser den.
Trin 7 - Vælg kanten AD med vægt 10. At inkludere denne kant vil også skabe cyklussen, så kasser den.
Så det endelige minimumspændende træ opnået fra den givne vægtede graf ved at bruge Kruskals algoritme er -
Prisen for MST er = AB + DE + BC + CD = 1 + 2 + 3 + 4 = 10.
Nu er antallet af kanter i ovenstående træ lig med antallet af hjørner 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 af Kruskals algoritme
Lad os nu se tidskompleksiteten af Kruskals algoritme.
Tidskompleksiteten af Kruskals algoritme er O(E logE) eller O(V logV), hvor E er nr. af kanter, og V er nr. af hjørner.
Implementering af Kruskals algoritme
Lad os nu se implementeringen af Kruskals algoritme.
Program: Skriv et program til at 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>