Introduzione

Benvenuto all’ultimo corso della serie Graph Algorithms! Come Kruskal, l’algoritmo di Prim costruisce un albero ricoprente minimo: l’insieme di archi meno costoso che collega ogni vertice senza formare cicli. I due algoritmi arrivano alla stessa soluzione seguendo percorsi diversi.

Prim fa crescere l’albero a partire da un vertice iniziale. A ogni passaggio aggiunge l’unico arco meno costoso che collega l’albero a un vertice che non ne fa ancora parte.

Il grafo è non orientato e pesato, ed è fornito come n (vertici da 0 a n - 1) e edges, un array piatto di triple [u0, v0, w0, ...] che rappresentano un arco non orientato u - v di peso w. Partiamo dal vertice 0.

Concludiamo la serie!