In questo articolo discuteremo dell'algoritmo di Kruskal. Qui vedremo anche la complessità, il funzionamento, l'esempio e l'implementazione dell'algoritmo di Kruskal.
Ma prima di passare direttamente all’algoritmo, dovremmo prima comprendere i termini di base come spanning tree e spanning tree minimo.
Albero di copertura - Uno spanning tree è il sottografo di un grafo connesso non orientato.
Albero di copertura minimo - L'albero di copertura minimo può essere definito come l'albero di copertura in cui la somma dei pesi del bordo è minima. Il peso dello spanning tree è la somma dei pesi dati ai bordi dello spanning tree.
Ora cominciamo con l'argomento principale.
Algoritmo di Kruskal viene utilizzato per trovare l'albero di copertura minimo per un grafico pesato connesso. L'obiettivo principale dell'algoritmo è trovare il sottoinsieme di archi mediante il quale possiamo attraversare ogni vertice del grafico. Segue l’approccio avido che trova una soluzione ottimale in ogni fase invece di concentrarsi su un ottimo globale.
Come funziona l'algoritmo di Kruskal?
Nell'algoritmo di Kruskal, iniziamo dagli spigoli con il peso più basso e continuiamo ad aggiungere gli spigoli fino al raggiungimento dell'obiettivo. I passaggi per implementare l'algoritmo di Kruskal sono elencati come segue:
- Per prima cosa, ordina tutti i bordi dal peso basso all'alto.
- Ora prendi il bordo con il peso più basso e aggiungilo allo spanning tree. Se il bordo da aggiungere crea un ciclo, allora rifiutare il bordo.
- Continua ad aggiungere i bordi finché non raggiungiamo tutti i vertici e viene creato un albero ricoprente minimo.
Le applicazioni dell'algoritmo di Kruskal sono:
- L'algoritmo di Kruskal può essere utilizzato per disporre i cavi elettrici tra le città.
- Può essere utilizzato per stabilire connessioni LAN.
Esempio dell'algoritmo di Kruskal
Ora vediamo il funzionamento dell'algoritmo di Kruskal utilizzando un esempio. Sarà più semplice comprendere l'algoritmo di Kruskal utilizzando un esempio.
Supponiamo che un grafico ponderato sia:
Il peso dei bordi del grafico sopra è riportato nella tabella seguente:
| Bordo | AB | AC | ANNO DOMINI | MA | AVANTI CRISTO | CD | DI |
| Peso | 1 | 7 | 10 | 5 | 3 | 4 | 2 |
Ora, ordina i bordi indicati sopra in ordine crescente in base al loro peso.
| Bordo | AB | DI | AVANTI CRISTO | CD | MA | AC | ANNO DOMINI |
| Peso | 1 | 2 | 3 | 4 | 5 | 7 | 10 |
Ora cominciamo a costruire l'albero di copertura minimo.
tipi di dati in Java
Passo 1 - Innanzitutto, aggiungi il bordo AB con peso 1 al MST.
Passo 2 - Aggiungi il bordo DI con peso 2 al MST poiché non sta creando il ciclo.
Passaggio 3: Aggiungi il bordo AVANTI CRISTO con peso 3 al MST, poiché non crea alcun ciclo o loop.
Passaggio 4: Ora scegli il bordo CD con peso 4 al MST, poiché non sta formando il ciclo.
Passaggio 5: Successivamente, scegli il bordo MA con peso 5. Includere questo bordo creerà il ciclo, quindi scartalo.
Passaggio 6: Scegli il bordo AC con peso 7. Includere questo bordo creerà il ciclo, quindi scartalo.
Passaggio 7: Scegli il bordo ANNO DOMINI con peso 10. Includere questo bordo creerà anche il ciclo, quindi scartalo.
Quindi, l'albero di copertura minimo finale ottenuto dal grafico ponderato dato utilizzando l'algoritmo di Kruskal è:
Il costo del MST è = AB + DE + BC + CD = 1 + 2 + 3 + 4 = 10.
Ora, il numero di spigoli nell'albero sopra è uguale al numero di vertici meno 1. Quindi, l'algoritmo si ferma qui.
Algoritmo
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
Complessità dell'algoritmo di Kruskal
Vediamo ora la complessità temporale dell'algoritmo di Kruskal.
La complessità temporale dell'algoritmo di Kruskal è O(E logE) o O(V logV), dove E è il n. di bordi e V è il n. di vertici.
Implementazione dell'algoritmo di Kruskal
Vediamo ora l'implementazione dell'algoritmo di Kruskal.
Programma: Scrivi un programma per implementare l'algoritmo di Kruskal in 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>