En aquest article, parlarem de l'algorisme de Kruskal. Aquí també veurem la complexitat, el funcionament, l'exemple i la implementació de l'algorisme de Kruskal.
Però abans d'avançar directament cap a l'algorisme, primer hauríem d'entendre els termes bàsics com ara l'arbre d'abast i l'arbre d'abast mínim.
arbre spanning - Un arbre spanning és el subgraf d'un graf connectat no dirigit.
Arbre spanning mínim - L'arbre spanning mínim es pot definir com l'arbre spanning en el qual la suma dels pesos de la vora és mínima. El pes de l'arbre spanning és la suma dels pesos donats a les vores de l'arbre spanning.
Ara, comencem pel tema principal.
Algoritme de Kruskal s'utilitza per trobar l'arbre d'abast mínim per a un gràfic ponderat connectat. L'objectiu principal de l'algorisme és trobar el subconjunt d'arestes mitjançant el qual podem recórrer tots els vèrtexs del gràfic. Segueix l'enfocament cobdiciós que troba una solució òptima en cada etapa en lloc de centrar-se en un òptim global.
Com funciona l'algoritme de Kruskal?
En l'algorisme de Kruskal, partim de les vores amb el pes més baix i anem afegint les vores fins que s'aconsegueix l'objectiu. Els passos per implementar l'algorisme de Kruskal s'enumeren a continuació:
- Primer, ordena totes les vores de baix pes a alt.
- Ara, agafeu la vora amb el pes més baix i afegiu-la a l'arbre allargat. Si la vora que cal afegir crea un cicle, rebutgeu la vora.
- Continueu afegint les vores fins que arribem a tots els vèrtexs i es creï un arbre d'abast mínim.
Les aplicacions de l'algorisme de Kruskal són:
- L'algoritme de Kruskal es pot utilitzar per dissenyar el cablejat elèctric entre les ciutats.
- Es pot utilitzar per establir connexions LAN.
Exemple de l'algorisme de Kruskal
Ara, vegem el funcionament de l'algorisme de Kruskal utilitzant un exemple. Serà més fàcil entendre l'algorisme de Kruskal utilitzant un exemple.
Suposem que un gràfic ponderat és -
El pes de les vores del gràfic anterior es mostra a la taula següent:
| Edge | AB | AC | AD | PERÒ | BC | CD | DE |
| Pes | 1 | 7 | 10 | 5 | 3 | 4 | 2 |
Ara, ordena les vores indicades anteriorment en l'ordre ascendent dels seus pesos.
| Edge | AB | DE | BC | CD | PERÒ | AC | AD |
| Pes | 1 | 2 | 3 | 4 | 5 | 7 | 10 |
Ara, comencem a construir l'arbre d'abast mínim.
igualtat de cadenes en java
Pas 1 - Primer, afegiu la vora AB amb pes 1 al MST.
Pas 2 - Afegiu la vora DE amb pes 2 al MST, ja que no està creant el cicle.
Pas 3 - Afegiu la vora BC amb pes 3 al MST, ja que no està creant cap cicle o bucle.
Pas 4 - Ara, trieu la vora CD amb pes 4 al MST, ja que no està formant el cicle.
Pas 5 - Després d'això, trieu la vora PERÒ amb pes 5. Incloure aquesta vora crearà el cicle, així que descarteu-lo.
Pas 6 - Trieu la vora AC amb pes 7. Incloure aquesta vora crearà el cicle, així que descarteu-lo.
Pas 7 - Trieu la vora AD amb pes 10. Incloure aquesta vora també crearà el cicle, així que descarteu-lo.
Per tant, l'arbre d'abast mínim final obtingut a partir del gràfic ponderat donat mitjançant l'ús de l'algorisme de Kruskal és -
El cost del MST és = AB + DE + BC + CD = 1 + 2 + 3 + 4 = 10.
Ara, el nombre d'arestes de l'arbre anterior és igual al nombre de vèrtexs menys 1. Per tant, l'algorisme s'atura aquí.
Algorisme
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
Complexitat de l'algorisme de Kruskal
Ara, vegem la complexitat temporal de l'algorisme de Kruskal.
La complexitat temporal de l'algorisme de Kruskal és O(E logE) o O(V logV), on E és el núm. d'arestes, i V és el núm. de vèrtexs.
Implementació de l'algorisme de Kruskal
Ara, vegem la implementació de l'algoritme de kruskal.
Programa: Escriu un programa per implementar l'algorisme de kruskal en 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>