U ovom ćemo članku raspravljati o Kruskalovom algoritmu. Ovdje ćemo također vidjeti složenost, rad, primjer i implementaciju Kruskalovog algoritma.
Ali prije nego što prijeđemo izravno na algoritam, prvo bismo trebali razumjeti osnovne pojmove kao što su razapinjuće stablo i minimalno razapinjuće stablo.
Razapinjuće stablo - Razapinjuće stablo je podgraf neusmjerenog povezanog grafa.
Minimalno razapinjuće stablo - Minimalno razapinjuće stablo može se definirati kao razapinjuće stablo u kojem je zbroj težina ruba minimalan. Težina razapinjućeg stabla zbroj je težina dodijeljenih rubovima razapinjućeg stabla.
Sada, počnimo s glavnom temom.
Kruskalov algoritam koristi se za pronalaženje minimalnog razapinjućeg stabla za povezani težinski graf. Glavni cilj algoritma je pronaći podskup bridova pomoću kojih možemo prijeći svaki vrh grafa. Slijedi pohlepan pristup koji pronalazi optimalno rješenje u svakoj fazi umjesto da se fokusira na globalni optimum.
Kako radi Kruskalov algoritam?
U Kruskalovom algoritmu počinjemo od rubova s najnižom težinom i nastavljamo dodavati rubove dok se ne postigne cilj. Koraci za implementaciju Kruskalovog algoritma navedeni su kako slijedi -
- Prvo razvrstajte sve rubove od male težine do velike.
- Sada uzmite rub s najnižom težinom i dodajte ga razapinjućem stablu. Ako rub koji se dodaje stvara ciklus, tada odbacite rub.
- Nastavite dodavati rubove dok ne dođemo do svih vrhova i stvori se minimalno razapinjuće stablo.
Primjene Kruskalovog algoritma su -
- Kruskalov algoritam može se koristiti za raspored električnih žica među gradovima.
- Može se koristiti za postavljanje LAN veza.
Primjer Kruskalovog algoritma
Sada, pogledajmo rad Kruskalovog algoritma koristeći primjer. Lakše ćemo razumjeti Kruskalov algoritam koristeći primjer.
Pretpostavimo da je ponderirani graf -
Težina rubova gornjeg grafa data je u donjoj tablici -
| Rub | AB | AC | OGLAS | ALI | PRIJE KRISTA | CD | OD |
| Težina | 1 | 7 | 10 | 5 | 3 | 4 | 2 |
Sada razvrstajte gore navedene rubove uzlaznim redoslijedom njihovih težina.
| Rub | AB | OD | PRIJE KRISTA | CD | ALI | AC | OGLAS |
| Težina | 1 | 2 | 3 | 4 | 5 | 7 | 10 |
Sada, počnimo konstruirati minimalno razapinjuće stablo.
prebacivanje metoda java
Korak 1 - Prvo dodajte rub AB s težinom 1 na MST.
Korak 2 - Dodajte rub OD s težinom 2 na MST jer ne stvara ciklus.
Korak 3 - Dodajte rub PRIJE KRISTA s težinom 3 na MST, jer ne stvara nikakav ciklus ili petlju.
Korak 4 - Sada odaberite rub CD s težinom 4 na MST, jer ne formira ciklus.
Korak 5 - Nakon toga odaberite rub ALI s težinom 5. Uključivanje ovog ruba stvorit će ciklus, stoga ga odbacite.
Korak 6 - Odaberite rub AC s težinom 7. Uključivanje ovog ruba stvorit će ciklus, stoga ga odbacite.
Korak 7 - Odaberite rub OGLAS s težinom 10. Uključivanje ovog ruba također će stvoriti ciklus, stoga ga odbacite.
Dakle, konačno minimalno razapinjuće stablo dobiveno iz danog ponderiranog grafa korištenjem Kruskalovog algoritma je -
Cijena MST-a je = AB + DE + BC + CD = 1 + 2 + 3 + 4 = 10.
Sada je broj bridova u gornjem stablu jednak broju vrhova minus 1. Dakle, algoritam ovdje staje.
Algoritam
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ženost Kruskalovog algoritma
Sada, da vidimo vremensku složenost Kruskalovog algoritma.
Vremenska složenost Kruskalovog algoritma je O(E logE) ili O(V logV), gdje je E broj. rubova, a V je br. od vrhova.
Implementacija Kruskalovog algoritma
Sada, da vidimo implementaciju Kruskalovog algoritma.
Program: Napišite program za implementaciju kruskalovog algoritma u 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>