Algorithme de Prim pour trouver un arbre de recouvrement minimal
Fondamental : Théorème sur lequel repose l'algorithme de Prim
On considère un graphe non orienté valué G=(X, E, V) ainsi que l'ensemble des arbres de recouvrement notés (X, F, V) de ce graphe.
On note (X, F, V)→(X',F',V) l'ensemble des arbres de recouvrement du graphe G=(X, E, V) qui contiennent l'arbre A=(X', F', V) du sous graphe (X', E', V) de (X, E, V)
(X' est strictement contenu dans X et F' est strictement contenu dans F).
Parmi les arbres de recouvrement minimaux du graphe (X, E, V) pour lesquels le sous-arbre A=(X', F', V) est imposé, il en existe au moins un qui contient l'arête de valeur minimale ayant une de ses extrémités dans X' et son autre extrémité dans X-X'.
Éléments de démonstration du théorème
Comme pour l'algorithme de Kruskal, la démonstration se fait par l'absurde.
Considérons un graphe G (dont les points sont dans X) et considérons un sous-graphe A de ce graphe (dont les points sont X') qui soit un arbre.
Soit F un arbre de recouvrement de G qui contient l'arbre A, mais qui ne contient aucune des arêtes de coût minimal dont une de ses extrémités est dans X et l'autre extrémité dans X'.
Soit b une des arêtes de coût minimal entre X et X'. Si on l'ajoute à l'arbre F, on crée obligatoirement un cycle. Ce cycle contient exactement deux arêtes ayant une extrémité dans X et une extrémité dans X', b et une autre arête c. Si on enlève c, on casse ce cycle. On a donc un graphe sans cycle de n-1 arêtes, c'est donc un arbre et comme le coût de b est strictement plus petit que celui de c, on a construit un arbre de recouvrement de poids strictement inférieur à celui de l'arbre minimal considéré qui n'était donc pas minimal.
Utilisation du théorème pour construire l'algorithme de Prim
On choisit arbitrairement n'importe quel point pour démarrer la construction de l'arbre, par exemple le point numéroté 1.
L'arbre A est alors constitué de ({1},Ø) c'est à dire le point 1 et pas d'arêtes.
On cherche dans le graphe G un des points dont la distance à 1 est la plus courte. Soit x ce point.
On met alors dans l'arbre le point x et l'arête joignant 1 à x. A=({1,x}, {{1,x}}).
Pour tous les points y autres que 1 et x (y n'est pas dans A), on calcule la distance la plus courte de y à A, c'est à dire la distance la plus courte entre y et 1 ou entre y et x.
Parmi ces points y, on retient un de ceux dont la distance de y à A est la plus courte et l'arête {y,z} qui assure cette distance minimale (avec z dans A).
On ajoute à A le point y dans l'ensemble des points et l'arête {y,z} dans l'ensemble des arêtes.
On recommence à chercher un nouveau point y qui n'est pas dans l'arbre et dont la distance à l'arbre est la plus courte et on l'ajoute à l'arbre ainsi que l'arête la plus courte qui relie y à l'arbre.
On itère cette opération jusqu'à ce que tous les points de X soient dans A. On a alors n points dans A et n-1 arêtes.
Les structures de données utilisées dans l'algorithme de Prim
On utilise deux tableaux de n éléments, où n est le nombre de points.
L'élément DISTANCE(i) contient -1 si i fait déjà partie de l'arbre en cours de construction A (i est dans X').
Dans l'animation, nous avons barré les cases correspondantes de manière à mieux voir les points non barrés de X-X'.
L'élément DISTANCE(i) contient +∞ s'il n'y a pas d'arête dans G qui relie le point i à l'arbre en cours de construction A.
L'élément DISTANCE(i) contient la longueur d'une des plus courtes arêtes de G qui relie le point i à un des points de X'.
L'élément PROX(i) contient - 1 si i fait déjà partie de l'arbre en cours de construction A (i est dans X').
Dans l'animation, nous avons barré les cases correspondantes de manière à mieux voir les points non barrés de X-X'.
L'élément PROX(i) contient 0 si i n'est pas dans X' et s'il n'y a pas d'arête dans G qui relie le point i à l'arbre en cours de construction A.
L'élément PROX(i) contient j un des points les plus proches de i dans l'arborescence en cours de construction A lorsqu'il existe au moins une arête entre i et l'arbre A.
R est l'ensemble des points de X-X'. Card(R) désigne le nombre d'éléments dans R.
F est l'ensemble des arêtes de l'arbre en cours de construction.
Description de l'algorithme de Prim
// Initialisation :
Pour tout i faire
DISTANCE(i)=+∞;
PROX(i)=-1
Finpourtout i;
// Le point 1 est choisi arbitrairement comme point de départ de l'arbre A.
// On suppose que V(i,j)= +∞ lorsque l'arête {i,j} n'existe pas.
Pour tout j faire
DISTANCE(j)=V(1,j) ;
si DISTANCE(j) == +∞
alors PROX(i)=0;
sinon PROX(i)=1;
finsi;
Finpourtout
DISTANCE(1)=-1 ;
PROX(1)=-1 ;
R=X-{1} ;
F=Ø ;
erreur = faux ;
// Itérations :
Tantque card(R) > 0 et erreur == faux faire
mini=+∞ ;
proche=0 ;
Pour tout j de R faire
si DISTANCE(j) < mini alors
mini=DISTANCE(j);
proche=j ;
finsi;
Finpourtout j ;
si proche == 0 alors
erreur = vrai;
sinon
R=R-{proche} ;
F=F U {{proche,PROX(proche)} ;
DISTANCE(proche)=-1 ;
PROX(proche)=-1 ;
// mise à jour de DISTANCE et de PROX
Pour tout j de R faire
si DISTANCE(j)>V(j,proche) alors
DISTANCE(j)=V(j,proche);
PROX(j)=proche fsi ;
finsi;
Finpourtout j ;
finsi
Fintantque ;
// Fin de l'algorithme
si erreur == faux alors
F contient les arêtes d'un arbre de recouvrement minimal
sinon
le graphe G n'était pas connexe
finsi;
Animation permettant de dérouler en pas à pas l'algorithme de Prim sur des exemples
Cliquez sur Anim pour démarrer l'animation. Vous pouvez ensuite sélectionner le graphe sur lequel vous souhaitez dérouler l'algorithme en pas à pas. Il est à noter que l'affichage de l'animation commence à la fin de la phase d'initialisation.
Complexité de l'algorithme de Prim
Il y a exactement n itérations principales et une boucle d'au plus n itérations à l'intérieur, c'est donc un algorithme polynomial en O(n2).
Remarque :
L'algorithme de Kruskal est donc intéressant quand il y a peu d'arêtes dans le graphe G alors que l'algorithme de Prim ne dépend pas du nombre d'arêtes et a une complexité constante lorsque le nombre de points est fixé.
