# Algorithme de Prim

L'algorithme de Prim est un algorithme glouton qui calcule un arbre couvrant minimal dans un graphe connexe pondéré et non orienté. En d'autres termes, cet algorithme trouve un sous-ensemble d'arêtes formant un arbre sur l'ensemble des sommets du graphe initial et tel que la somme des poids de ces arêtes soit minimale. Si le graphe n'est pas connexe, alors l'algorithme détermine un arbre couvrant minimal d'une composante connexe du graphe.

## Historique

L'algorithme a été développé en 1930 par le mathématicien tchèque Vojtech Jarnik, puis a été redécouvert et republié par Robert C. Prim et Edsger W. Dijkstra en 1959. Ainsi, il est parfois appelé DJP algorithm, Jarník's algorithm, Prim–Jarník algorithm, ou Prim–Dijkstra algorithm.

## Principe

L'algorithme consiste à faire croître un arbre depuis un sommet. On part d'un sous-ensemble contenant un sommet unique. À chaque itération, on agrandit ce sous-ensemble en prenant l'arête incidente à ce sous-ensemble de coût minimum. En effet, si l'on prend une arête dont les deux extrémités appartiennent déjà à l'arbre, l'ajout de cette arête créerait un deuxième chemin entre les deux sommets dans l'arbre en cours de construction et le résultat contiendrait un cycle.

## Exemple

À droite, on donne un exemple d'exécution de l'algorithme de Prim.

## Pseudo-code

Le pseudo-code de l'algorithme de Prim est similaire à celui de l'algorithme de Dijkstra et utilise le type abstrait file de priorité.
Au début tous les sommets sont dans la file de priorité. La priorité est donnée par cout[.]. Autrement dit, le sommet possédant la plus faible valeur dans le tableau cout[.] sortira en premier de la file. On retire un à un les sommets de la file de priorité. Le tableau pred[.] contient le prédécesseur d'un sommet dans l'arbre en construction. L'algorithme retourne le tableau pred qui représente l'arbre couvrant de poids minimum.

## Complexité

On effectue $|V|$ opérations défiler et $2|E|$ opérations réduire priorité, où $|V|$ est le nombre de sommets dans le graphe et $|E|$ est le nombre d'arcs dans le graphe. Si l'on regarde la complexité de ces deux opérations avec trois possibilités de files de priorités, on obtient les complexités ci-dessous :
| File de priorité | Graphe | Complexité temporelle |
| liste ou tableau | matrice d'adjacence | $O(|V|^{2})$ |
| tas min binaire | liste d'adjacence | $O((|V|+|E|)\log |V|)=O(|E|\log |V|)$ |
| tas de Fibonacci | liste d'adjacence | $O(|E|+|V|\log |V|)$ |

## Preuve de correction

Soit G un graphe connexe pondéré. À chaque itération de l'algorithme de Prim, on trouve une arête qui connecte un sommet dans un sous-graphe à un sommet à l'extérieur du sous-graphe. Puisque G est connexe, il y aura toujours un chemin vers tous les sommets. La sortie Y de l'algorithme de Prim est un arbre, parce que chaque sommet (sauf le premier) est relié à exactement un prédécesseur.
Soit A$_i$ l'ensemble des i premières arêtes ajoutées à l'arbre Y par l'algorithme de Prim et A$_0$ =. On va montrer que, pour chacun des A$_i$, il existe un arbre couvrant minimal de G contenant A$_i$. Alors il existera un arbre couvrant minimum qui contiendra Y et sera donc Y. Pour ce faire, supposons qu'il existe un premier ensemble A$_k$ tel qu'aucun arbre couvrant minimal ne contient A$_k$. Soit e l'arête qui appartient à A$_k$ mais n'appartient pas à A$_{k-1}$, soit Y$_1$ un arbre couvrant minimum du graphe G qui contient toutes les arêtes d' A$_{k-1}$ et soit S l'ensemble de sommets reliés par les arêtes d' A$_{k-1}$. Une extrémité de l'arête e est dans l'ensemble S et l'autre n'est pas. Puisque l'arbre Y$_1$ est un arbre couvrant du graphe G, il y a un chemin dans l'arbre Y$_1$ joignant les deux extrémités de e. Lorsque l'on se déplace le long du chemin, on doit rencontrer une arête f qui joint un sommet de S à un sommet qui n'est pas dans l'ensemble S. Alors, à l'itération où l'arête e a été ajoutée à l'arbre Y, l'arête f pourrait aussi avoir été ajoutée et elle serait ajoutée au lieu de e si son poids était moins que celui de e, et puisque l'arête f n'a pas été ajoutée, nous concluons que
$w(f)\geq w(e).$
Soit Y$_2$ l'arbre obtenu en enlevant l'arête f et en ajoutant l'arête e à l'arbre Y$_1$. Il est facile de montrer que l'arbre Y$_2$ est un arbre couvrant et le poids total de ses arêtes n'est pas supérieur à celui de l'arbre Y$_1$ et que Y$_2$ contient toutes les arêtes d' A$_k$. On arrive à une contradiction, car on a supposé qu'il existe un ensemble A$_k$ tel qu'aucun arbre couvrant de poids minimum ne contient les arêtes d' A$_k$. C'est donc que l'hypothèse faite est fausse.