logo

TechCodeview

Kruskalov algoritem

V tem članku bomo razpravljali o Kruskalovem algoritmu. Tukaj bomo videli tudi kompleksnost, delovanje, primer in implementacijo Kruskalovega algoritma.

Toda preden se premaknemo neposredno k algoritmu, moramo najprej razumeti osnovne izraze, kot sta vpeto drevo in minimalno vpeto drevo.

Vpeto drevo - Vpeto drevo je podgraf neusmerjenega povezanega grafa.

Najmanjše vpeto drevo - Minimalno vpeto drevo lahko definiramo kot vpeto drevo, v katerem je vsota uteži roba minimalna. Teža vpetega drevesa je vsota uteži robov vpetega drevesa.

Zdaj pa začnimo z glavno temo.

Kruskalov algoritem se uporablja za iskanje najmanjšega vpetega drevesa za povezan uteženi graf. Glavni cilj algoritma je najti podmnožico robov, s pomočjo katerih lahko prečkamo vsako vozlišče grafa. Sledi pohlepnemu pristopu, ki najde optimalno rešitev na vsaki stopnji, namesto da bi se osredotočil na globalni optimum.

Kako deluje Kruskalov algoritem?

V Kruskalovem algoritmu začnemo z robovi z najmanjšo težo in dodajamo robove, dokler ne dosežemo cilja. Koraki za implementacijo Kruskalovega algoritma so navedeni na naslednji način -

  • Najprej razvrstite vse robove od majhne teže do visoke.
  • Zdaj vzemite rob z najnižjo težo in ga dodajte vpetemu drevesu. Če rob, ki ga želite dodati, ustvari cikel, zavrnite rob.
  • Nadaljujte z dodajanjem robov, dokler ne dosežemo vseh oglišč in ustvarimo minimalno vpeto drevo.

Uporabe Kruskalovega algoritma so -

  • Kruskalov algoritem se lahko uporablja za postavitev električne napeljave med mesti.
  • Uporablja se lahko za vzpostavitev LAN povezav.

Primer Kruskalovega algoritma

Zdaj pa si poglejmo delovanje Kruskalovega algoritma na primeru. Na primeru bomo lažje razumeli Kruskalov algoritem.

Recimo, da je uteženi graf -

Kruskal

Teža robov zgornjega grafa je podana v spodnji tabeli -

Edge AB AC AD AMPAK pr. n. št CD OF
Utež 1 7 10 5 3 4 2

Zdaj razvrstite zgornje robove po naraščajočem vrstnem redu njihovih uteži.

Edge AB OF pr. n. št CD AMPAK AC AD
Utež 1 2 3 4 5 7 10

Zdaj pa začnimo graditi minimalno vpeto drevo.

xor cpp

Korak 1 - Najprej dodajte rob AB s težo 1 na MST.

Kruskal

2. korak - Dodajte rob OF s težo 2 na MST, ker ne ustvarja cikla.

Kruskal

3. korak - Dodajte rob pr. n. št s težo 3 na MST, saj ne ustvarja nobenega cikla ali zanke.

Kruskal

4. korak - Zdaj izberite rob CD s težo 4 na MST, saj ne tvori cikla.

Kruskal

5. korak - Po tem izberite rob AMPAK s težo 5. Če vključite ta rob, boste ustvarili cikel, zato ga zavrzite.

6. korak - Izberi rob AC s težo 7. Če vključite ta rob, boste ustvarili cikel, zato ga zavrzite.

7. korak - Izberi rob AD s težo 10. Če vključite ta rob, boste ustvarili tudi cikel, zato ga zavrzite.

Torej, končno minimalno vpeto drevo, pridobljeno iz danega uteženega grafa z uporabo Kruskalovega algoritma, je -

Kruskal

Cena MST je = AB + DE + BC + CD = 1 + 2 + 3 + 4 = 10.

Zdaj je število robov v zgornjem drevesu enako številu vozlišč minus 1. Torej, algoritem se tukaj ustavi.

Algoritem

 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

Kompleksnost Kruskalovega algoritma

Zdaj pa poglejmo časovno kompleksnost Kruskalovega algoritma.

    Časovna zapletenost
    Časovna kompleksnost Kruskalovega algoritma je O(E logE) ali O(V logV), kjer je E št. robov, V pa je št. vozlišč.

Implementacija Kruskalovega algoritma

Zdaj pa si oglejmo izvedbo kruskalovega algoritma.

Program: Napišite program za implementacijo Kruskalovega algoritma v 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 &gt;&gt; edges; for(int i = 0;i <edges;++i) { cout<> x &gt;&gt; y &gt;&gt; weight; p[i] = make_pair(weight, make_pair(x, y)); } sort(p, p + edges); minimumCost = kruskal(p); cout &lt;<'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&apos;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>