Calculateur Algorithme de Prim

Pseudocode

Prim fait croître un seul arbre depuis un départ arbitraire. À chaque étape il prend l'arête la moins chère ayant exactement une extrémité déjà dans l'arbre, ce qui suffit à garantir l'optimalité sans jamais revenir en arrière.

Prim(graphe, depart):
    dansArbre = {depart}
    fp = file de priorite des aretes sortant de depart
    acm = []

    tant que dansArbre ne contient pas tous les sommets:
        (u, v, w) = fp.extraireMin()
        si v dans dansArbre: continuer   // arete perimee

        acm.ajouter((u, v, w))
        dansArbre.ajouter(v)
        pour chaque arete (v, x, w2):
            si x hors de dansArbre: fp.inserer((v, x, w2))

La correction repose sur la propriété de coupe: pour toute partition des sommets en deux côtés, l'arête la moins chère traversant cette coupe appartient à un arbre couvrant de poids minimum. Prim l'applique avec la coupe « déjà dans l'arbre » contre « pas encore », et c'est pourquoi prendre l'arête traversante la moins chère est toujours sûr. Cette propriété explique aussi pourquoi aucun retour en arrière n'est nécessaire: une arête acceptée ne peut jamais devenir un mauvais choix à la lumière d'informations ultérieures, contrairement à ce qui arrive dans un problème comme le TSP.

Exemple détaillé, étape par étape

Fais croître un arbre couvrant de poids minimum depuis A sur un petit graphe pondéré où le choix glouton rejette délibérément une arête directe en apparence moins chère.

Graphe d'exemple: Arêtes non orientées A-B (2), A-C (3), B-C (1), C-D (4) et B-D (7).

1. Démarrer en A. L'arbre ne contient que A. Les arêtes qui en sortent sont A-B à 2 et A-C à 3. Toutes deux traversent la coupe entre {A} et le reste.
2. Prendre A-B (2). A-B est l'arête traversante la moins chère, donc B rejoint l'arbre. La frontière contient désormais A-C à 3, B-C à 1 et B-D à 7.
3. Prendre B-C (1). B-C à 1 est maintenant l'arête traversante la moins chère, moins chère que la directe A-C à 3, donc C rejoint l'arbre en passant par B. L'arête directe A-C n'est jamais utilisée. C'est l'étape à observer: un sommet adjacent au départ n'est pas nécessairement relié via le départ.
4. A-C devient interne. A et C étant tous deux dans l'arbre, l'arête A-C a désormais ses deux extrémités à l'intérieur et se trouve écartée quand elle remonte. C'est le test des entrées périmées qui joue son rôle.
5. Prendre C-D (4). Les arêtes traversantes restantes sont C-D à 4 et B-D à 7. C-D est moins chère, donc D rejoint l'arbre, qui couvre alors les quatre sommets et l'algorithme s'arrête.

L'arbre couvrant de poids minimum est A-B, B-C et C-D pour un poids total de 2 + 1 + 4 = 7. Remarque qu'il compte exactement trois arêtes, une de moins que les quatre sommets, comme tout arbre couvrant. Remarque aussi qu'ici l'arbre est un chemin, ce qui rappelle qu'un arbre couvrant de poids minimum n'est pas un arbre de plus courts chemins: la distance de A à D dans l'arbre vaut 7, alors que le plus court chemin A vers C vers D dans le graphe vaut 3 + 4 = 7 et A vers B vers D vaut 9. Les deux problèmes optimisent des quantités différentes, et confondre les deux est l'erreur conceptuelle la plus fréquente sur ce sujet.

Complexité et son origine

Temps: O(E log V) · Espace: O(V + E)

Avec un tas binaire, chaque arête peut être insérée une fois et extraite une fois en O(log E), et comme E vaut au plus V au carré, log E reste à un facteur constant de log V, d'où O(E log V). Chaque sommet est ajouté à l'arbre exactement une fois, ce qui borne le nombre d'itérations de la boucle externe à V. Un tas de Fibonacci avec diminution de clé au lieu d'insertion paresseuse améliore la borne en O(E + V log V), asymptotiquement meilleur sur les graphes denses, mais les constantes le rendent rarement rentable en pratique. Sur un graphe très dense, l'option la plus simple l'emporte: conserver un tableau de l'arête la moins chère connue vers chaque sommet extérieur et le parcourir à chaque tour donne O(V au carré), ce qui bat O(E log V) dès que E approche V au carré. Le choix de structure de données est donc dicté par la densité, pas par une préférence générale.

Quand utiliser Algorithme de Prim, et quand l'éviter

Prim et Kruskal produisent tous deux un arbre couvrant de poids minimum. Le bon choix dépend de la densité, de l'ordre d'arrivée des arêtes et de la connexité du graphe.

Pièges fréquents

• Confondre arbre couvrant minimum et arbre de plus courts chemins. Ce sont des objectifs distincts. Un ACM minimise le poids total de l'arbre entier; un arbre de plus courts chemins minimise la distance depuis une source vers chaque sommet. Dans l'exemple ci-dessus, le trajet de A à D dans l'ACM coûte 7 en arêtes de l'arbre, et de façon générale un ACM peut éloigner certaines paires bien plus que nécessaire. Si ce qui t'intéresse est la distance depuis un point donné, c'est Dijkstra qu'il faut, pas Prim.
• Omettre le test des entrées périmées. Un tas paresseux accumule des arêtes dont l'extrémité lointaine finit par rejoindre l'arbre par un autre chemin. En extraire une et l'ajouter crée un cycle et détruit l'arbre. Vérifie toujours si la cible est déjà dans l'arbre avant d'accepter une arête, exactement comme la garde équivalente dans Dijkstra.
• L exécuter sur un graphe non connexe. Prim fait croître un arbre depuis un départ et s'arrête quand il ne trouve plus d'arête traversante. Sur un graphe non connexe il renvoie donc un arbre couvrant d'une seule composante, sans signaler d'erreur. S'il te faut une forêt couvrante de poids minimum, relance depuis chaque sommet non visité, ou utilise Kruskal, qui gère ce cas nativement.
• Supposer que l ACM est unique. Quand plusieurs arêtes partagent un poids, il peut exister de nombreux arbres couvrants de poids minimum, tous de même total. L'arbre n'est unique que si tous les poids sont distincts. Les tests doivent comparer le poids total, jamais l'ensemble d'arêtes, faute de quoi ils échoueront sur des implémentations parfaitement correctes.
• L appliquer à un graphe orienté. Les arbres couvrants au sens de Prim et Kruskal sont une notion non orientée. L'analogue orienté est l'arborescence couvrante de poids minimum, qui nécessite l'algorithme de Chu-Liu/Edmonds; Prim y donne des réponses fausses sans le signaler.

Questions fréquentes

À quoi sert l'algorithme de Prim?

Il trouve un arbre couvrant de poids minimum: l'ensemble d'arêtes le moins coûteux reliant tous les sommets d'un graphe non orienté pondéré. Il sert à concevoir des réseaux à faible coût, réseaux électriques, tracés de fibre et de télécommunications, canalisations d'eau et routage de circuits, et il sous-tend également le regroupement par lien simple et certaines méthodes de segmentation d'images.

Quelle est la complexité temporelle de l'algorithme de Prim?

O(E log V) avec un tas binaire, l'implémentation habituelle. Un tas de Fibonacci donne O(E + V log V), asymptotiquement meilleur sur les graphes denses mais avec de moins bonnes constantes. Sur les graphes très denses, un simple parcours de tableau en O(V au carré) est en réalité plus rapide car il évite entièrement le coût du tas.

Quelle est la différence entre les algorithmes de Prim et de Kruskal?

Prim fait croître un unique arbre connexe vers l'extérieur depuis un sommet de départ, en ajoutant toujours l'arête la moins chère atteignant un nouveau sommet. Kruskal trie toutes les arêtes et ajoute celles qui ne ferment pas de cycle, faisant croître une forêt qui fusionne en un arbre. Prim convient aux graphes denses, Kruskal aux graphes creux ou aux arêtes prétriées, et les deux donnent un arbre couvrant de poids minimum.

Un arbre couvrant minimum est-il la même chose qu'un arbre de plus courts chemins?

Non. Un ACM minimise le poids total de ses arêtes; un arbre de plus courts chemins minimise la distance depuis une source vers chaque sommet. Ils diffèrent souvent, et un ACM peut laisser deux sommets très éloignés en distance dans l'arbre alors qu'une arête directe courte existe, parce que l'utiliser augmenterait le total.

Le sommet de départ change-t-il le résultat?

Il peut changer quelles arêtes sont retenues en cas d'égalité de poids, mais jamais le poids total. Prim produit un arbre couvrant de poids minimum depuis n'importe quel départ. Si tous les poids sont distincts, l'arbre est unique et le sommet de départ n'a aucune influence.