Algoritmo Kruskal
Albero di spanning minimo
Un grafico che non ha direzioni è chiamato grafico non diretto. Ogni grafico deve avere un percorso da un nodo a un altro nodo. Un albero di spanning è anche un grafico collegato non orientato in cui tutti i nodi del grafico sono presenti con bordi minimi. Se un albero che spanning non ha tutti i nodi del grafico, allora non possiamo dire che si tratti di un albero che attraversa. I pesi totali di spanning-tree saranno inferiori al peso originale del grafico mentre l'abbiamo collegato attraverso i bordi di peso minimo. L'albero che spinge non ha un ciclo. Qualsiasi grafico ha più di un albero che si estende, ma solo uno di questi sarà unico. Lo chiamiamo un albero di spanning minimo poiché stiamo tentando di creare un grafico completo con tutti i nodi mantenendo il peso basso.
Comprendiamo il minimo che lo spanning Tree con un esempio. Quindi, come sappiamo, l'albero di spanning minimo fa parte del grafico ma con meno costi. Quindi questo scenario può essere illustrato con un esempio. Supponiamo che abbiamo un grafico come questo.
Il grafico sopra può essere disposto in diversi modi in modo che il ciclo del grafico venga rimosso, altrimenti non sarà un MST (albero di spanning minimo). Quindi rimuoveremo il ciclo dal grafico e conterremo il costo totale del grafico. Abbiamo quattro nodi, o vertici (A, B, C e D).
Caso 1:
Dopo aver rimosso il ciclo dal grafico, il costo del grafico MST sopra (albero di spanning minimo) è 56.
Caso -2:
Dopo aver rimosso il ciclo dal grafico, il costo del grafico MST (albero di spanning minimo) sopra è 53.
Caso - 3:
Dopo aver rimosso il ciclo dal grafico, il costo grafico MST (albero di spanning minimo) sopra è 41.
Possiamo vedere che l'ultimo grafico del costo totale del caso 3 è molto più basso rispetto agli altri due grafici. Quindi questo grafico è il nostro MST finale (albero di spanning minimo) per il grafico originale. Il motivo degli algoritmi di Prim o Kruskal è trovare il costo del grafico il più basso possibile. Quindi questo è il nostro motivo in questo articolo per spiegare questo MST.
Possiamo disegnare un albero che sparnisce con l'aiuto dei seguenti due metodi:
- L'algoritmo di Kruskal
- L'algoritmo di Prim
In questo articolo, discuteremo dell'algoritmo di Kruskal. L'algoritmo di Prim sarà discusso nel prossimo articolo.
L'algoritmo di Kruskal
L'algoritmo di Kruskal è molto facile da implementare rispetto all'algoritmo di Prim perché non dobbiamo preoccuparci dei vertici di adiacenza in questo algoritmo. In questo algoritmo, l'algoritmo di Kruskal inizia da tutti i vertici del grafico. Scegliamo la vertice del bordo del peso minimo e iniziamo a creare l'albero di spanning minimo. Scegliamo un altro bordo con il peso minimo e lo aggiungiamo all'albero di spanning minimo. Questo processo continua fino a quando non aggiungiamo tutti i nodi grafici originali. Una volta che tutti i nodi nel grafico vengono aggiunti all'albero di spanning minimo, l'algoritmo si fermerà. Durante la creazione dell'albero di spanning minimo di un grafico, dobbiamo anche occuparci di quel grafico, non creando alcun ciclo perché i cicli non dovrebbero essere nell'albero di spanning minimo.
Quindi, se un nodo crea il ciclo nell'albero di spanning minimo, scegliamo l'altro nodo, anche se il peso di questo nodo è maggiore del nodo precedente che crea il ciclo.
L'algoritmo di Kruskal è diverso dall'algoritmo di Prim. L'algoritmo di Prim, mentre si crea un albero di spanning minimo, parte da qualsiasi nodo o vertice e quindi aggiunge un altro nodo o vertice solo dai nodi di adiacenza. Ma l'algoritmo di Kruskal non si preoccupa del nodo di adiacenza e seleziona sempre quel nodo che ha meno peso, ma quel nodo non dovrebbe creare un ciclo nell'albero minimo.
Passaggi dell'algoritmo di Kruskal:
Vengono prese le seguenti fasi mentre si scrive il codice C ++ per l'algoritmo di Kruskal.
- Creiamo un array per archiviare gruppi di nodi o vertici del grafico.
- Creiamo un altro array per archiviare i pesi dei bordi grafici.
- Per l'albero che spinge, creiamo un nuovo array.
- Organizziamo l'array dei bordi in ordine crescente.
- Ripetiamo il passaggio 6 fino a quando l'array di pesi del bordo ordinato non è vuota.
- Confrontiamo i due gruppi fianco a fianco. In questo caso, se un nodo di un gruppo non corrisponde all'altro nodo, aggiungiamo quel bordo all'albero che si spinge e lo aggiungiamo nello stesso gruppo.
- Iterare attraverso tutti i bordi dell'albero che si spingono per determinare il suo peso totale.
Ora implementeremo i passaggi dell'algoritmo di cui sopra usando un esempio. Abbiamo il grafico seguente e scopriremo l'albero minimo per questo grafico.
Quindi, secondo l'algoritmo, scegliamo per la prima volta il bordo di peso più piccolo, che è AB. Quindi abbiamo scelto quel bordo e lo abbiamo tenuto nell'array di alberi da spanning. Il peso del bordo AB è 9.
Ora, scegliamo il prossimo bordo, CD e manteniamo quel bordo nel vano antro per alberi da spanning minimo. Il peso del bordo del CD è 12.
Il prossimo bordo più piccolo che abbiamo ottenuto era BC, che abbiamo tenuto nell'array. Il bordo BC ponderato è 17.
Il nostro algoritmo si fermerà qui perché abbiamo tutti i vertici di un grafico e abbiamo il nostro albero di spanning minimo. Il peso totale di questo MST è 9 + 12 + 17 = 38.
Programma: Il seguente è un codice C ++ per l'algoritmo di Kruskal.
#includere#includere
#includere
Classe Edgegraph
pubblico:
int nodestart;
int nodeEnd;
int wght;
EdgeGraph ()
EdgeGraph (int node_1, int node_2, int peso): nodestart (node_1),
nodeend (node_2), wght (peso)
;
bool confrontEdGost (const Edgegraph A, const Edgegraph b)
restituire a.wght < b.wght;
Classe G
privato:
int num_of_nodes;
Std :: Vector
Std :: Vector
Std :: Vector
pubblico:
G()
G (int num_of_nodes)
this-> num_of_nodes = num_of_nodes;
parentele.RASIZE (NUM_OF_NODES);
Ranknode.RASIZE (NUM_OF_NODES);
vuoto addGegraph (Edgegraph e);
int findParsNode (int nodo);
void kruskalmst_algo (std :: vector
void DisplayEdgeGraphs (std :: vector
;
void g :: addGegraph (Edgegraph e)
Edgegraphlist.push_back (e);
int g :: findParsNode (int nodo)
if (nodo != parenteNode [nodo])
parenteNode [node] = findParsNode (parentNode [nodo]);
restituire parenternode [nodo];
void G :: DisplayEdgeGraphs (std :: vector
int costo = 0;
std :: cout << "EdgeGraphs of MST : ";
per (auto & e: mst)
std :: cout << "[" << e.nodeSTART << "-" << e.nodeEND
<< "](" << e.wght << ") ";
Costo += E.wght;
std :: cout << "\n Kruskal MST Cost : " << cost << std :: endl;
// Questa è la funzione algoritmo principale di Kruskal che cerca
// l'albero minimo di spanning.
void g :: kruskalmst_algo (std :: vector
per (int i = 0; i
RankNode [i] = 0;
Ordina (EdgeGraphlist.inizio (), EdgeGraphlist.FINE(),
Paragonedgecost);
per (auto & e: EdgeGraphlist)
int root_1 = findParsNode (e.NODESTART);
int root_2 = findParsNode (e.nodeEnd);
if (root_1 != root_2)
risultato.push_back (e);
if (RankNode [root_1] < rankNode[root_2])
parenteNode [root_1] = root_2;
RankNode [root_2] ++;
altro
parenteNode [root_2] = root_1;
RankNode [root_1] ++;
int main ()
int num_of_nodes = 6; // (0, 1, 2, 3, 4, 5)
Edgegraph E1 (0, 1, 4);
Edgegraph E2 (0, 2, 1);
Edgegraph E3 (0, 3, 5);
Edgegraph E4 (1, 3, 2);
Edgegraph E5 (1, 4, 3);
Edgegraph E6 (1, 5, 3);
Edgegraph E7 (2, 3, 2);
Edgegraph E8 (2, 4, 8);
Edgegraph E9 (3, 4, 1);
Edgegraph E10 (4, 5, 3);
G g1 (num_of_nodes);
G1.Addgegraph (E1);
G1.Addgegraph (E2);
G1.Addgegraph (E3);
G1.Addgegraph (E4);
G1.Addgegraph (E5);
G1.Addgegraph (E6);
G1.Addgegraph (E7);
G1.Addgegraph (E8);
G1.Addgegraph (E9);
G1.Addgegraph (E10);
Std :: Vector
G1.Kruskalmst_algo (MST);
G1.DisplayEdgeGraphs (MST);
restituzione 0;
Produzione:
Edgegraphs di MST: [0-2] (1) [3-4] (1) [1-3] (2) [2-3] (2) [1-5] (3)Kruskal MST Costo: 9
Conclusione:
Abbiamo studiato il minimo albero da spanning di Kruskal, che è la prima preferenza della maggior parte delle persone quando devono trovare il grafico MST da un grafico. L'algoritmo di Kruskal è semplice da capire e implementare in un'applicazione del mondo reale. Come l'algoritmo di Prim, anche l'algoritmo di Kruskal è molto utile nelle applicazioni di vita reale. Quindi dobbiamo capire questo algoritmo.