Algoritmo Prims

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. Anche l'albero 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.

Possiamo disegnare un albero che sparnisce con l'aiuto dei seguenti due metodi:

1. L'algoritmo di Kruskal
2. L'algoritmo di Prim

In questo articolo, discuteremo dell'algoritmo di Prim. L'algoritmo di Kruskal sarà discusso nel prossimo articolo.

Algoritmo di Prim:

L'algoritmo di Prim viene utilizzato per trovare l'albero minimo di un grafico. L'algoritmo di Prim inizia da qualsiasi nodo e quindi aggiunge qualsiasi nodo adiacente il cui peso è il minimo e questo processo continua fino a quando tutti i nodi nei grafici non vengono visitati. Quando creano l'albero di spanning minimo di un grafico, non dobbiamo anche creare alcun ciclo perché i cicli non dovrebbero essere nell'albero minimo.

Passaggi dell'algoritmo di Prim:

L'algoritmo di Prim impiega l'approccio avido per l'albero minimo. Dobbiamo scegliere qualsiasi vertice del grafico e quindi scegliere il vertice di adiacenza successivo il cui peso è inferiore e continuiamo questo processo fino a quando non ci colleghiamo l'intero grafico.

Passo 1: Scegli qualsiasi vertice di origine nel grafico.

Passo 2: Trova il bordo di peso minimo adiacente alla sorgente e quindi collegalo all'albero che si spinge.

Passaggio 3: Ripeti il ​​passaggio 2 fino a quando tutti i nodi non vengono aggiunti nell'albero di spanning minimo.

Esempio :

Il seguente è un esempio per cercare un albero di spanning minimo usando l'algoritmo di Prim.

1. Scegliamo qualsiasi nodo casuale dal grafico G e lo aggiungiamo al MST (albero di spanning minimo). Selezioniamo qui nodo 0.

2. Ora, selezioniamo quel bordo adiacente al nodo di origine (0) ma con il peso più piccolo, quindi aggiungiamo quel nodo di peso più piccolo all'albero minimo.

3. Ora, selezioniamo quel bordo adiacente al nodo di origine (0 o 1) ma con il peso più piccolo, quindi aggiungiamo quel nodo di peso più piccolo all'albero di spanning minimo.

4. Ora, selezioniamo quel bordo adiacente al nodo di origine (0, 1 o 3) ma con il peso più piccolo, quindi aggiungiamo quel nodo di peso più piccolo all'albero di spanning minimo.

5. Ora, selezioniamo quel bordo adiacente al nodo di origine (0, 1, 3 o 4) ma con il peso più piccolo, e quindi aggiungiamo quel nodo di peso più piccolo all'albero minimo.

6. Ora, selezioniamo quel bordo adiacente al nodo di origine (0, 1, 3, 4 o 6) ma con il peso più piccolo, quindi aggiungiamo quel nodo di peso più piccolo all'albero minimo.

7. Ora, selezioniamo quel bordo adiacente al nodo di origine (0, 1, 3, 4, 6 o 2) ma con il peso più piccolo, quindi aggiungiamo quel nodo di peso più piccolo all'albero minimo.

Sopra è il nostro MST finale (albero di spanning minimo) e il costo totale è 6.

Il programma MST (albero spanning minimo) di C ++ Prim:

#includere
#includere
#includere
#includere
#includere
typedef std :: coppia Sii;
typedef std :: vector Ssii;
int primsmst (int sourcenode, std :: vector & grafico)
// Questa coda memorizzerà i dettagli di ciascun nodo
// insieme al loro valore di peso.
std :: priority_queue, std :: maggiore> K;
K.push (std :: make_pair (0, sourcenode));
bool nodesadded [grafico.misurare()];
memset (nodesadded, false, sizeof (bool)*grafico.misurare());
int mst_tree_cost = 0;
Mentre (!K.vuoto())
// Stiamo selezionando qui il nodo che ha un costo minimo
SII ItemNode;
ItemNode = k.superiore();
K.pop();
int node = itemNode.secondo;
int cost = itemNode.Primo;
// Qui stiamo verificando se non è stato aggiunto un nodo al MST,
// quindi aggiungendo quel nodo.
Se (!nodedded [nodo])
mst_tree_cost += cost;
nodedded [nodo] = true;
// iterare sui nodi negativi che sono stati recentemente presi
// fuori dalla coda prioritaria.
// e aggiunto al MST che non è ancora aggiunto
for (Auto & pail_node_cost: grafico [nodo])
int addacy_node = pail_node_cost.secondo;
if (nodeSAdded [addacy_node] == false)
K.push (coppie_node_cost);




restituire mst_tree_cost;

int main ()
// I dettagli del grafico con il nodo di costo e aggeggio.
SSII fromnode_0_in_graph_1 = 1,1, 2,2, 1,3,
1,4, 2,5, 1,6;
SSII fromnode_1_in_graph_1 = 1,0, 2,2, 2,6;
SSII fromnode_2_in_graph_1 = 2,0, 2,1, 1,3;
SSII fromnode_3_in_graph_1 = 1,0, 1,2, 2,4;
SSII fromnode_4_in_graph_1 = 1,0, 2,3, 2,5;
SSII fromnode_5_in_graph_1 = 2,0, 2,4, 1,6;
SSII fromnode_6_in_graph_1 = 1,0, 2,2, 1,5;
int num_of_nodes = 7; // nodi totali (da 0 a 6)
Std :: Vector primsgraph;
primsgraph.RASIZE (NUM_OF_NODES);
primsgraph [0] = fromnode_0_in_graph_1;
primsgraph [1] = fromnode_1_in_graph_1;
primsgraph [2] = fromnode_2_in_graph_1;
primsgraph [3] = fromnode_3_in_graph_1;
primsgraph [4] = fromnode_4_in_graph_1;
primsgraph [5] = fromnode_5_in_graph_1;
primsgraph [6] = fromnode_6_in_graph_1;
// Come già sappiamo, dobbiamo scegliere il vertice di origine,
// Quindi iniziamo dal nodo Vertex 0.
std :: cout << "Total cost of minimum spanning tree after Prim's algorithm : "
"" << PrimsMST(0, primsgraph) << std :: endl;
restituzione 0;

Produzione:

Costo totale dell'albero di spanning minimo dopo l'algoritmo di Prim: 6

Complessità temporale dell'algoritmo MST di Prim:

1. Il tempo totale richiesto per elaborare e selezionare il nodo coda di priorità specifica che deve ancora essere aggiunto all'MST è logv.Ma mentre funziona per ogni vertice, la complessità del tempo totale è V (logV).

2. Il grafico non è indirizzato e i bordi totali saranno 2e. Dato che dobbiamo spingere i nodi nella coda prioritaria, ci vorrà un registro temporale totale (V). Tuttavia, poiché abbiamo un totale di bordi 2E, la nostra operazione di spinta totale sarà 2E (log (v)).

3. Complessità totale dopo l'operazione 1 e 2 è O ((e + v) log (v)).

Conclusione:

Abbiamo studiato il minimo dell'albero di spanning di Prim, che è la prima preferenza della maggior parte delle persone quando devono trovare il grafico MST da un grafico. L'algoritmo di Prim è semplice da comprendere e implementare in un'applicazione del mondo reale.L'algoritmo di Prim è molto utile nelle applicazioni di vita reale, ad esempio collegando binari ferroviari a tutto le città. Quindi è solo un singolo esempio, ma la sua applicazione è enorme, quindi dobbiamo capire questo algoritmo.