Introduction

Bienvenue dans le dernier cours de la série Algorithmes de graphes ! Comme Kruskal, l'algorithme de Prim construit un arbre couvrant de poids minimal : l'ensemble d'arêtes le moins coûteux qui relie chaque sommet sans cycle. Les deux algorithmes parviennent au même résultat par des chemins différents.

Prim fait croître l'arbre vers l'extérieur à partir d'un sommet de départ. À chaque étape, il ajoute l'arête la moins chère qui relie l'arbre à un sommet qui n'y figure pas encore.

Le graphe est non orienté et pondéré, donné sous la forme de n (sommets de 0 à n - 1) et edges, un tableau plat de triplets [u0, v0, w0, ...] pour une arête non orientée u - v de poids w. Nous commençons à partir du sommet 0.

Terminons la série !