Tässä artikkelissa keskustelemme Kruskalin algoritmista. Täällä näemme myös Kruskal-algoritmin monimutkaisuuden, toimivuuden, esimerkin ja toteutuksen.
Mutta ennen kuin siirrymme suoraan kohti algoritmia, meidän pitäisi ensin ymmärtää perustermit, kuten virittävä puu ja minimivirittävän puu.
Virtaava puu - Virittävä puu on suuntaamattoman yhdistetyn graafin osagraafi.
Vähimmäisvirtapuu - Pienin virittävä puu voidaan määritellä virittäväksi puuksi, jossa reunan painojen summa on pienin. Virittävän puun paino on virittävän puun reunoihin annettujen painojen summa.
Aloitetaan nyt pääaiheesta.
Kruskalin algoritmi käytetään etsimään liitetyn painotetun graafin minimi virittävä puu. Algoritmin päätavoitteena on löytää se reunojen osajoukko, jonka avulla voimme kulkea graafin jokaisen kärjen läpi. Se noudattaa ahneutta, joka löytää optimaalisen ratkaisun joka vaiheessa sen sijaan, että keskittyisi globaaliin optimiin.
Miten Kruskalin algoritmi toimii?
Kruskalin algoritmissa lähdetään liikkeelle pienimmän painoisista reunoista ja lisätään reunoja, kunnes tavoite saavutetaan. Vaiheet Kruskalin algoritmin toteuttamiseksi on lueteltu seuraavasti -
- Lajittele ensin kaikki reunat kevyestä korkeaan.
- Ota nyt pienin painoinen reuna ja lisää se ulottuvaan puuhun. Jos lisättävä reuna luo jakson, hylkää reuna.
- Jatka reunojen lisäämistä, kunnes saavutamme kaikki kärjet ja luodaan pienin virittävä puu.
Kruskalin algoritmin sovellukset ovat -
- Kruskalin algoritmia voidaan käyttää sähköjohdotuksen järjestämiseen kaupunkien välillä.
- Sitä voidaan käyttää LAN-yhteyksien muodostamiseen.
Esimerkki Kruskalin algoritmista
Katsotaan nyt Kruskalin algoritmin toimintaa esimerkin avulla. Kruskalin algoritmi on helpompi ymmärtää esimerkin avulla.
Oletetaan, että painotettu kaavio on -
Yllä olevan kaavion reunojen paino on annettu alla olevassa taulukossa -
| Reuna | AB | AC | ILMOITUS | MUTTA | eKr | CD | OF |
| Paino | 1 | 7 | 10 | 5 | 3 | 4 | 2 |
Lajittele nyt edellä annetut reunat painonsa mukaan nousevaan järjestykseen.
| Reuna | AB | OF | eKr | CD | MUTTA | AC | ILMOITUS |
| Paino | 1 | 2 | 3 | 4 | 5 | 7 | 10 |
Aloitetaan nyt pienimmän virittävän puun rakentaminen.
java dynaaminen taulukko
Vaihe 1 - Lisää ensin reuna AB painon kanssa 1 MST:lle.
Vaihe 2 - Lisää reuna OF painon kanssa 2 MST:lle, koska se ei luo sykliä.
Vaihe 3 - Lisää reuna eKr painon kanssa 3 MST:hen, koska se ei luo sykliä tai silmukkaa.
Vaihe 4 - Valitse nyt reuna CD painon kanssa 4 MST:hen, koska se ei muodosta kiertoa.
Vaihe 5 - Valitse sen jälkeen reuna MUTTA painon kanssa 5. Tämän reunan sisällyttäminen luo syklin, joten hylkää se.
Vaihe 6 - Valitse reuna AC painon kanssa 7. Tämän reunan sisällyttäminen luo syklin, joten hylkää se.
Vaihe 7 - Valitse reuna ILMOITUS painon kanssa 10. Tämän reunan sisällyttäminen luo myös syklin, joten hylkää se.
Joten lopullinen pienin virittävä puu, joka saadaan annetusta painotetusta graafista Kruskalin algoritmilla, on -
MST:n hinta on = AB + DE + BC + CD = 1 + 2 + 3 + 4 = 10.
Nyt edellä olevan puun reunojen määrä on yhtä suuri kuin kärkien lukumäärä miinus 1. Joten algoritmi pysähtyy tähän.
Algoritmi
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
Kruskalin algoritmin monimutkaisuus
Katsotaan nyt Kruskalin algoritmin aikamonimutkaisuus.
Kruskalin algoritmin aikamonimutkaisuus on O(E logE) tai O(V logV), missä E on no. reunoista, ja V on nro. pisteistä.
Kruskalin algoritmin toteutus
Katsotaan nyt kruskalin algoritmin toteutusta.
Ohjelmoida: Kirjoita ohjelma kruskalin algoritmin toteuttamiseksi C++:ssa.
#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>