- Attuale
- Nell'albero
- Vicino all'albero
- Miglior arco finora
Algoritmo di Prim
L'algoritmo di Prim costruisce un albero ricoprente minimo, l'insieme di archi più economico che collega tutti i nodi, facendo crescere un solo albero da una partenza. A ogni passo aggiunge il nodo che si raggiunge dall'albero con l'arco più corto. Fai clic su un nodo per partire da lì e procedi passo per passo per vedere i nodi in attesa, i loro archi migliori e l'albero che cresce. Premi Avvia per guardare l'albero crescere, oppure Passo e Indietro per procedere un passo alla volta. Trascina il cursore dei passi per saltare dove vuoi. Fai clic su un nodo per farne la partenza: l'albero cresce da lì. Il numero su ogni arco è la sua lunghezza. Sotto il grafo ci sono i nodi in attesa, ognuno con la lunghezza del suo arco migliore verso l'albero, che è tratteggiato. Nuovo grafo crea un altro grafo; scegli quanti nodi e archi deve avere. Con il riquadro selezionato, le frecce vanno avanti e indietro di un passo, la barra spaziatrice avvia e mette in pausa, e Home e Fine saltano all'inizio e alla fine.
Come funziona
- Fai clic su un nodo per farne la partenza: l'albero cresce da lì.
- Premi Avvia, oppure usa Passo e Indietro per procedere un passo alla volta. Trascina il cursore dei passi per saltare in qualsiasi punto.
- Osserva i nodi in attesa sotto il grafo, ognuno con il suo arco migliore verso l'albero. Nuovo grafo crea un altro grafo da provare.
Come funziona l'algoritmo di Prim
Parti da un albero di un solo nodo. Ogni nodo fuori dall'albero ricorda il suo arco più corto verso l'albero, se ne ha uno. Prendi ogni volta il nodo con l'arco più corto, aggiungilo all'albero insieme a quell'arco ed esamina i suoi archi: se uno è più corto del miglior arco finora di un vicino, diventa il miglior arco di quel vicino. Quando tutti i nodi sono entrati, l'albero ha un arco in meno dei nodi, e la sua lunghezza totale è la minima possibile.
Prim e Dijkstra
L'algoritmo di Prim e l'algoritmo di Dijkstra sono quasi uguali: entrambi fanno crescere una regione da una partenza e tengono i nodi in attesa in una coda di priorità. La differenza è il numero nella coda. Dijkstra tiene l'intera distanza di ogni nodo dalla partenza; Prim solo la lunghezza del suo arco migliore verso l'albero. Così Dijkstra costruisce un albero dei percorsi più brevi, e Prim un albero di lunghezza totale minima, e spesso i due alberi sono diversi.
Domande frequenti
Che cos'è l'algoritmo di Prim?
Un algoritmo greedy che costruisce un albero ricoprente minimo di un grafo pesato facendo crescere un solo albero da un nodo di partenza, aggiungendo sempre l'arco più corto che collega l'albero a un nodo esterno.
Il nodo di partenza conta?
Solo per l'ordine: da qualsiasi partenza, l'algoritmo di Prim finisce con un albero ricoprente della stessa lunghezza totale minima. Se alcuni archi hanno la stessa lunghezza, l'albero stesso può essere diverso.
Chi ha inventato l'algoritmo di Prim?
Vojtěch Jarník lo descrisse per primo, nel 1930. Robert Prim lo riscoprì nel 1957 ed Edsger Dijkstra nel 1959, per questo si chiama anche algoritmo di Jarník o algoritmo di Prim–Jarník.
Quanto è veloce l'algoritmo di Prim?
Con un heap binario, il lavoro cresce come E log V per V nodi ed E archi. Con un semplice array al posto dell'heap servono circa V² passi, il che è meglio per i grafi densi, dove quasi ogni coppia di nodi è collegata.
Il mio grafo viene inviato da qualche parte?
No. Il grafo viene creato e l'albero costruito nel tuo browser, e le tue ultime impostazioni restano nella memoria locale di questo browser.
Pronto a provarlo?
Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.
Vai all'editor