- Actuel
- Dans l'arbre
- Voisin de l'arbre
- Meilleure arête jusqu'ici
Algorithme de Prim
L'algorithme de Prim construit un arbre couvrant minimal, l'ensemble d'arêtes le moins cher qui relie tous les nœuds, en faisant grandir un seul arbre depuis un départ. À chaque étape, il ajoute le nœud que l'arbre atteint par la plus courte arête. Cliquez sur un nœud pour partir de là et avancez pas à pas pour voir les nœuds en attente, leurs meilleures arêtes et l'arbre qui grandit. Appuyez sur Lecture pour voir l'arbre grandir, ou sur Étape et Retour pour avancer pas à pas. Faites glisser le curseur d'étapes pour aller n'importe où. Cliquez sur un nœud pour en faire le départ : l'arbre grandit à partir de lui. Le nombre sur chaque arête est sa longueur. Sous le graphe se trouvent les nœuds en attente, chacun avec la longueur de sa meilleure arête vers l'arbre, tracée en pointillés. Nouveau graphe crée un autre graphe ; choisissez son nombre de nœuds et d'arêtes. Quand le plateau est sélectionné, les flèches avancent ou reculent d'une étape, la barre d'espace lance et met en pause, et Origine et Fin vont au début et à la fin.
Comment ça marche
- Cliquez sur un nœud pour en faire le départ : l'arbre grandit à partir de lui.
- Appuyez sur Lecture, ou utilisez Étape et Retour pour avancer pas à pas. Faites glisser le curseur d'étapes pour aller n'importe où.
- Observez les nœuds en attente sous le graphe, chacun avec sa meilleure arête vers l'arbre. Nouveau graphe crée un autre graphe à essayer.
Fonctionnement de l'algorithme de Prim
Commencez par un arbre d'un seul nœud. Chaque nœud hors de l'arbre retient sa plus courte arête vers l'arbre, s'il en a une. Prenez à chaque fois le nœud dont l'arête est la plus courte, ajoutez-le à l'arbre avec cette arête, et examinez ses arêtes : si l'une d'elles est plus courte que la meilleure arête d'un voisin jusqu'ici, elle devient la meilleure arête de ce voisin. Quand tous les nœuds ont rejoint l'arbre, il a une arête de moins qu'il n'y a de nœuds, et sa longueur totale est la plus petite possible.
Prim et Dijkstra
L'algorithme de Prim et l'algorithme de Dijkstra se ressemblent beaucoup : tous deux font grandir une région depuis un départ et gardent les nœuds en attente dans une file de priorité. La différence est le nombre dans la file. Dijkstra garde la distance entière de chaque nœud depuis le départ ; Prim garde seulement la longueur de sa meilleure arête vers l'arbre. Dijkstra construit donc un arbre de plus courts chemins, et Prim un arbre de plus petite longueur totale, et les deux arbres sont souvent différents.
Questions fréquemment posées
Qu'est-ce que l'algorithme de Prim ?
Un algorithme glouton qui construit un arbre couvrant minimal d'un graphe pondéré en faisant grandir un seul arbre depuis un nœud de départ, en ajoutant toujours la plus courte arête qui relie l'arbre à un nœud extérieur.
Le nœud de départ compte-t-il ?
Seulement pour l'ordre : quel que soit le départ, l'algorithme de Prim finit avec un arbre couvrant de même longueur totale minimale. Quand des arêtes ont la même longueur, l'arbre lui-même peut changer.
Qui a inventé l'algorithme de Prim ?
Vojtěch Jarník l'a décrit le premier, en 1930. Robert Prim l'a redécouvert en 1957 et Edsger Dijkstra en 1959 : on l'appelle donc aussi algorithme de Jarník ou algorithme de Prim–Jarník.
L'algorithme de Prim est-il rapide ?
Avec un tas binaire, son travail croît en E log V pour V nœuds et E arêtes. Avec un simple tableau au lieu d'un tas, il faut environ V² étapes, ce qui est mieux pour les graphes denses, où presque toutes les paires de nœuds sont reliées.
Mon graphe est-il envoyé quelque part ?
Non. Le graphe est créé et l'arbre construit dans votre navigateur, et vos derniers réglages restent dans le stockage local de ce navigateur.
Prêt à l'essayer ?
Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.
Aller à l'éditeur