logo

TechCodeview

Algoritmul lui Kruskal

În acest articol, vom discuta despre algoritmul lui Kruskal. Aici, vom vedea, de asemenea, complexitatea, funcționarea, exemplul și implementarea algoritmului lui Kruskal.

Dar înainte de a trece direct la algoritm, ar trebui să înțelegem mai întâi termenii de bază, cum ar fi spanning tree și spanning tree minim.

Arborele spanning - Un arbore de întindere este subgraful unui graf conectat nedirecționat.

Arborele de întindere minim - Arborele de întindere minim poate fi definit ca arborele de întindere în care suma greutăților marginii este minimă. Greutatea arborelui spanning este suma greutăților date marginilor arborelui spanning.

Acum, să începem cu subiectul principal.

Algoritmul lui Kruskal este folosit pentru a găsi arborele de acoperire minim pentru un grafic ponderat conectat. Ținta principală a algoritmului este găsirea subsetului de muchii prin care putem traversa fiecare vârf al graficului. Urmează abordarea lacomă care găsește o soluție optimă în fiecare etapă, în loc să se concentreze pe un optim global.

Cum funcționează algoritmul lui Kruskal?

În algoritmul lui Kruskal, începem de la muchiile cu cea mai mică greutate și continuăm să adăugăm marginile până când obiectivul este atins. Pașii pentru implementarea algoritmului lui Kruskal sunt enumerați după cum urmează -

  • Mai întâi, sortați toate marginile de la greutate mică la mare.
  • Acum, luați marginea cu cea mai mică greutate și adăugați-o la arborele care se întinde. Dacă marginea care trebuie adăugată creează un ciclu, atunci respingeți marginea.
  • Continuați să adăugați marginile până ajungem la toate vârfurile și se creează un arbore de acoperire minim.

Aplicațiile algoritmului lui Kruskal sunt:

  • Algoritmul lui Kruskal poate fi folosit pentru a dispune cablarea electrică între orașe.
  • Poate fi folosit pentru a stabili conexiuni LAN.

Exemplu de algoritm al lui Kruskal

Acum, să vedem funcționarea algoritmului lui Kruskal folosind un exemplu. Va fi mai ușor de înțeles algoritmul lui Kruskal folosind un exemplu.

Să presupunem că un grafic ponderat este -

Kruskal

Greutatea marginilor graficului de mai sus este dată în tabelul de mai jos -

Margine AB AC ANUNȚ DAR î.Hr CD DE
Greutate 1 7 10 5 3 4 2

Acum, sortați marginile indicate mai sus în ordinea crescătoare a greutăților lor.

Margine AB DE î.Hr CD DAR AC ANUNȚ
Greutate 1 2 3 4 5 7 10

Acum, să începem să construim arborele de întindere minim.

matrice bash

Pasul 1 - Mai întâi, adăugați marginea AB cu greutate 1 la MST.

Kruskal

Pasul 2 - Adăugați marginea DE cu greutate 2 la MST, deoarece nu creează ciclul.

Kruskal

Pasul 3 - Adăugați marginea î.Hr cu greutate 3 la MST, deoarece nu creează niciun ciclu sau buclă.

Kruskal

Pasul 4 - Acum, alege marginea CD cu greutate 4 la MST, deoarece nu formează ciclul.

Kruskal

Pasul 5 - După aceea, alegeți marginea DAR cu greutate 5. Includerea acestei margini va crea ciclul, așa că aruncați-l.

Pasul 6 - Alege marginea AC cu greutate 7. Includerea acestei margini va crea ciclul, așa că aruncați-l.

Pasul 7 - Alege marginea ANUNȚ cu greutate 10. Includerea acestei margini va crea și ciclul, așa că aruncați-l.

Deci, arborele de acoperire minim final obținut din graficul ponderat dat folosind algoritmul lui Kruskal este -

Kruskal

Costul MST este = AB + DE + BC + CD = 1 + 2 + 3 + 4 = 10.

Acum, numărul de muchii din arborele de mai sus este egal cu numărul de vârfuri minus 1. Deci, algoritmul se oprește aici.

Algoritm

 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

Complexitatea algoritmului lui Kruskal

Acum, să vedem complexitatea în timp a algoritmului lui Kruskal.

    Complexitatea timpului
    Complexitatea temporală a algoritmului lui Kruskal este O(E logE) sau O(V logV), unde E este nr. de muchii, iar V este nr. de vârfuri.

Implementarea algoritmului lui Kruskal

Acum, să vedem implementarea algoritmului lui kruskal.

Program: Scrieți un program pentru a implementa algoritmul lui kruskal în 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>